Results 1 to 4 of 4

Math Help - Odd prime division problem

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    Odd prime division problem

    Prove that if  p \neq 5 is an odd prime, prove that either p^2-1 or p^2+1 is divisible by 10.

    My proof so far:

    If 10 | p^2-1, then we are done. Assume 10 doesn't divide p^2-1.

    Let p=2n+1 for some integer n. Then p^2+1 = (2n+1)^2+1=4n^2+4n+1+1=4n^2+4n+2 so 2 can divide it.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by tttcomrader View Post
    Prove that if  p \neq 5 is an odd prime, prove that either p^2-1 or p^2+1 is divisible by 10.

    My proof so far:

    If 10 | p^2-1, then we are done. Assume 10 doesn't divide p^2-1.

    Let p=2n+1 for some integer n. Then p^2+1 = (2n+1)^2+1=4n^2+4n+1+1=4n^2+4n+2 so 2 can divide it.
    Let for an odd prime p \equiv 1,\ 3,\ 5,\ 7,\ \mbox{ or }\ 9 \mod 10; so p^2 \equiv 1,\ 5,\ \mbox{ or }\ 9 \mod 10 .

    But as p is a prime other than 5,\ p \not\equiv 5 \mod 10 and so p^2 \not\equiv 5 \mod 10 .

    Hence:

    p^2 \equiv 1,\ \mbox{ or }\ 9 \mod 10

    which proves the required result.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2
    So far our course have not introduce mod yet, is it possible to do this by other means? thank you.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by tttcomrader View Post
    Prove that if  p \neq 5 is an odd prime, prove that either p^2-1 or p^2+1 is divisible by 10.

    My proof so far:

    If 10 | p^2-1, then we are done. Assume 10 doesn't divide p^2-1.

    Let p=2n+1 for some integer n. Then p^2+1 = (2n+1)^2+1=4n^2+4n+1+1=4n^2+4n+2 so 2 can divide it.
    A number has one of the forms: 10k,10k+1,...,10k+9.
    Now examine each of these forms.

    1) 10k this is never prime.
    2) 10k+2 = 2(5k+1) this is only prime for k=0, but the prime is odd so it cannot have this form.
    3) 10k+3 since 3,10 have no common factors this is a possible prime.
    4) 10k+4 = 2(5k+2) this is never prime.
    5) 10k+5 = 5(2k+1) this is only prime at k=0 and that prime is 5 which cannot be because p\not = 5.
    6) 10k+6 = 2(5k+3) this is never prime.
    7) 10k+7 a possible prime.
    8) 10k+8 = 2(5k+4) this is never prime.
    9) 10k+9 a possible prime.


    Which means p has one of three forms: 10k+3,10k+7,10k+9. If you substitute that into p^2 \pm 1 you will see it is divisible by 10. For example, (10k+3)^2 = 10(10k+6)+9 so p^2 + 1 is divisible. And so on.

    I just realized I forgot 10k+1 - but you get the idea. And do not be afraid of this argument, it might look long but that is because I explained it in detail.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Division by a prime ≡ 3 (mod 4)
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 5th 2010, 12:39 AM
  2. division problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: August 24th 2010, 05:02 PM
  3. Division problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 5th 2009, 07:29 PM
  4. Division Problem
    Posted in the Algebra Forum
    Replies: 7
    Last Post: April 3rd 2008, 08:19 AM
  5. Division Problem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: January 19th 2007, 06:20 AM

Search Tags


/mathhelpforum @mathhelpforum