Results 1 to 3 of 3

Math Help - 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 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: 24=2^3\cdot{3} so we'll prove that n^2-1\equiv{0}(\bmod.8) (1) and n^2-1\equiv{0}(\bmod.3) (2)

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

    (1) We have: n^2-1=(n-1)\cdot{(n+1)}, but since n is odd, then either n\equiv{1}(\bmod.4) or n\equiv{3}(\bmod.4) so either n-1 or 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; July 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: February 20th 2010, 06:14 PM
  2. Modulo Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 7th 2009, 09:52 AM
  3. Congruence & Modulo Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 15th 2009, 06:00 PM
  4. Modulo proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 16th 2008, 04:22 PM
  5. proof on inverse modulo
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 16th 2006, 05:42 PM

Search Tags


/mathhelpforum @mathhelpforum