Results 1 to 4 of 4

Thread: Odd prime division problem

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

    Odd prime division problem

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

    My proof so far:

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

    Let p=2n+1 for some integer n. Then $\displaystyle 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
    5
    Quote Originally Posted by tttcomrader View Post
    Prove that if $\displaystyle p \neq 5$ is an odd prime, prove that either $\displaystyle p^2-1$ or $\displaystyle p^2+1$ is divisible by 10.

    My proof so far:

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

    Let p=2n+1 for some integer n. Then $\displaystyle 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 $\displaystyle p \equiv 1,\ 3,\ 5,\ 7,\ \mbox{ or }\ 9 \mod 10$; so $\displaystyle p^2 \equiv 1,\ 5,\ \mbox{ or }\ 9 \mod 10 $.

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

    Hence:

    $\displaystyle 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
    10
    Quote Originally Posted by tttcomrader View Post
    Prove that if $\displaystyle p \neq 5$ is an odd prime, prove that either $\displaystyle p^2-1$ or $\displaystyle p^2+1$ is divisible by 10.

    My proof so far:

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

    Let p=2n+1 for some integer n. Then $\displaystyle 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: $\displaystyle 10k,10k+1,...,10k+9$.
    Now examine each of these forms.

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


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

    I just realized I forgot $\displaystyle 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: Nov 5th 2010, 12:39 AM
  2. division problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Aug 24th 2010, 05:02 PM
  3. Division problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 5th 2009, 07:29 PM
  4. Division Problem
    Posted in the Algebra Forum
    Replies: 7
    Last Post: Apr 3rd 2008, 08:19 AM
  5. Division Problem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Jan 19th 2007, 06:20 AM

Search Tags


/mathhelpforum @mathhelpforum