Results 1 to 3 of 3

Thread: Modulo proof help

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    13

    Modulo proof help

    Let n be an odd integer not divisible by three. Prove that n^2 is congruent 1 mod 24.

    I started by assuming that n is an odd integer divisible by three. So I want to show that n^2 is NOT congruent to 1 mod 24. If n is odd then there exists an integer k such that n=2k+1. so n^2= 4k^2 +4k+1. Now where do I go from here?!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    That doesn't work, because you are proving that if $\displaystyle n^2-1$ is multiple of 24, then n is not multiple of 3. That doesn't prove that the assertion is true, there could be no such integers 'n'.

    First note that: $\displaystyle 24=2^3\cdot{3}$ so we'll prove that $\displaystyle n^2-1\equiv{0}(\bmod.8)$ (1) and $\displaystyle n^2-1\equiv{0}(\bmod.3)$ (2)

    (2) Follows easily from Fermat's Little Theorem since $\displaystyle (n,3)=1$, or you can check the 2 possible cases $\displaystyle n\equiv{1;2}(\bmod.3)$

    (1) We have: $\displaystyle n^2-1=(n-1)\cdot{(n+1)}$, but since $\displaystyle n$ is odd, then either $\displaystyle n\equiv{1}(\bmod.4)$ or $\displaystyle n\equiv{3}(\bmod.4)$ so either $\displaystyle n-1$ or $\displaystyle n+1$ is multiple of 4, but both are even, thus the product must be multiple of 8, since one is multiple of 4 and the other even.
    Last edited by PaulRS; Jul 14th 2008 at 06:34 PM. Reason: Typo. 4->8
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2008
    Posts
    13
    Thanks so much!!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modulo Question: Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 20th 2010, 06:14 PM
  2. Modulo Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 7th 2009, 09:52 AM
  3. Congruence & Modulo Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 15th 2009, 06:00 PM
  4. Modulo proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jul 16th 2008, 04:22 PM
  5. proof on inverse modulo
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Oct 16th 2006, 05:42 PM

Search Tags


/mathhelpforum @mathhelpforum