Question 1151775: (a) Let p be a prime number greater than 3. What are the possible remainders of p upon division by 6? (b) What are the possible values of n^2 (mod 6) for an odd integer n? (c) Show that if 2^n + n^2 is a prime greater than 3, then n ≡ 3 (mod 6).
Answer by jim_thompson5910(35256)   (Show Source):
You can put this solution on YOUR website!
I'll do part (a) to get you started.
p is some prime number such that p > 3.
We are dividing this prime by 6 to get
p/6 = q+r/6
q = quotient
r = remainder
the quotient and remainder are integers
Multiply both sides by 6
p = 6q + r
The remainder r can be any one of these values {0,1,2,3,4,5}
If r is even, r = 0,2,4, then we can show that p itself is even
For instance, if r = 2, then
p = 6q+r
p = 6q+2
p = 2(3q+1)
p = some multiple of 2
but p has to be odd in order for it to be a prime number larger than 3.
So we can rule out any cases when r is even.
This leaves r = 1,3 or 5.
But if r = 3, then,
p = 6q+r
p = 6q+3
p = 3(2q+1)
showing that 3 is a factor of p, therefore invalidating p being a prime number
A prime number only has factors of 1 and itself
We can rule out r = 3.
So r = 1 or r = 5 are the only remainders possible.
Here is a table of some primes mod 6
| p | p mod 6 |
| 5 | 5 |
| 7 | 1 |
| 11 | 5 |
| 13 | 1 |
| 17 | 5 |
| 23 | 5 |
| 29 | 5 |
| 31 | 1 |
| 37 | 1 |
| 41 | 5 |
| 43 | 1 |
|
|
|
