Re: 2(p^2)+1 = 0 mod 3 for any prime p != 3

David P Jablon (dpj@world.std.com)
Wed, 25 Mar 1998 16:16:27 -0500

• Next message: Ron Rivest: "More efficient chaffing technique"
• Previous message: Tim Dierks: "Re: 2(p^2)+1 = 0 mod 3 for any prime p != 3"

Hamdi asks to prove that for any prime p where p != 3,
        2(p^2) + 1 = 0 mod 3.

I'll use "~=" to mean "equivalent, modulo 3".

First, the special case when p = 2:
2(p^2) + 1 = 2(4^2) + 1
        = 9
        ~= 0.

Otherwise, p is an odd prime > 3.

Let n = (p-1)/2.

2(p^2) + 1 = 2((2n+1)^2) + 1
        = 2(4n^2 + 4n + 1) + 1
        = 8n^2 + 8n + 3
        ~= 8(n^2 + n)

We only have to look at three cases:

If n = 0 mod 3,
2(p^2) + 1 ~= 8(n^2 + n)
        ~= 8(0 + 0)
        ~= 0.

If n = 2 mod 3, then for some integer k,
2(p^2) + 1 ~= 8(n^2 + n)
        ~= 8((3k+2)^2 + 3k + 2)
        ~= 8(9k^2 + 15k + 6)
        ~= 8(0 + 0 + 0)
        ~= 0.

If n = 1 mod 3, then for some integer k,
2(p^2) + 1 = 8(n^2 + n) + 3
        = 8((3k+1)^2 + 3k+1) + 3
        = 8(9k^2 + 9k + 2) + 3
        = 72k^2 + 72k + 19.
2(p^2)+1 = 9(8k^2 + 8k + 2) + 1
2(p^2) = 9(8k^2 + 8k + 2)
2(p^2) = 9(8k^2 + 8k + 2)
p^2 = 9 (4k^2 + 4k + 1)
and taking the square root of each side
p = 3 * sqrt(4k^2 + 4k + 1)

This case is impossible. Here p is either a
multiple of 3, or an irrational, contradicting the
assumption that p is a prime greater than 3.
Thus, n != 1 mod 3.

QED.

(Sometimes I just get the urge to do other people's homework. :-)

-- dpj

------------------------------------------------------
David P. Jablon
dpj@world.std.com
<http://world.std.com/~dpj/>

• Next message: Ron Rivest: "More efficient chaffing technique"
• Previous message: Tim Dierks: "Re: 2(p^2)+1 = 0 mod 3 for any prime p != 3"