SOLUTION: (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

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

RELATED QUESTIONS
Let $p$ be a prime. What are the possible remainders when $p$ is divided by $17?$... (answered by Edwin McCravy)

Let n be a positive integer, k the number of prime numbers less than or equal to n, and... (answered by richard1234)

three items were randomely selected from a bin that contains 3 defective and 7... (answered by stanbon)

A single die is rolled. What is the probability of rolling the following: (a) P(4) (b)... (answered by stanbon)

A salesperson has a 50% chance of making a sale to any customer called upon. If 4 calls... (answered by ewatrrr)

Question: If a die is rolled one time, find this probability: Of getting a number... (answered by stanbon)

Numbers 1,2,3,4,5,6,7,8,9 are written on seperate cards. The cards are shuffled and the... (answered by jrfrunner)

when a student subtracts 7 from a number, the result is greater than 5/3 of the number.... (answered by ewatrrr)

John wants his friends to figure out what number he is thinking of. He gives them three... (answered by fcabanski)