Question

Find all prime numbers p, so that number 8p^2 + 1 would be prime.

Answer 1

What I have tried:
prime numbers bigger than 3 (actually, I noticed that one answer for this question is 2) can be written as 6n +- 1, so p = 6n +- 1
substituting that to 8p^2 + 1 and removing all the brackets would get 288n^ + 96n + 9. However, how would I get a number out of this?

Answer 2

I think that it might have something to do with even numbers, since one answer is 2, but I can't prove anything with it, as I can see it now...

Answer 3

288n^2 + 96n + 9 can be simplified to 9(32n^2 +- 11n + 1), however that doesn't get me anywhere :/

Answer 4

Familiar with modular arithmetic ?

Answer 5

Just the basics.

Answer 6

That'll do

Answer 7

8p^2 + 1

Answer 8

What's the remainder when 8 is divided by 3 ?

Answer 9

2

Answer 10

Notice that 2 is same as -1 in modulus 3

Answer 11

Okay.

Answer 12

8p^2 + 1 is same as -p^2 + 1 in modulus 3

Answer 13

Yes.

Answer 14

Suppose p is not 3

Answer 15

But wait, wouldnt modulus affect + 1 as well?

Answer 16

So, just -p^2

Answer 17

-p^2 - 1

Answer 18

Who ate +1 ?

Answer 19

8p^2 + 1 is same as -p^2 + 1 in modulus 3

Answer 20

Hm, okay.

Answer 21

Oh! I was quite dumb ;( I was wondering why + 1 doesn't get modified, but 1 / 3 reminder is 1... Dumb me!

Answer 22

Maybe forget the modular arithmetic.
Lets use anoyher method that doesn't use modular arithmetic

Answer 23

Okay, but after that show me modular way as well ;)

Answer 24

Okay sure

Answer 25

Let's start over

Answer 26

Suppose p is not 3 and consider all other primes in modulus 3

Answer 27

They will be of form 3k+1 or 3k+2

Answer 28

Yes ?

Answer 29

Yes

Answer 30

But 3k+2 is same as 3k-1 in modulus 3

Answer 31

So, 3k +- 1

Answer 32

So every prime greater than 3 will be of form 3k +- 1

Answer 33

Yes.

Answer 34

Look at the given expression
8p^2 + 1

Answer 35

Replace p by 3k +- 1

Answer 36

72k^2 + 48k + 9

Answer 37

3(25k^2 + 16k + 3)

Answer 38

That means there are no primes of such bigger than 3?

Answer 39

That's it.
Oh wait, looka your initial attempt is also exactly same as this

Answer 40

Yes, I just failed to multiply everything right to check that 2 isn't the prime needed ;D
And my initial attempt overlooked 5 as well, so your work is better.

Answer 41

But I wonder, why did you take 3, not some other number?

Answer 42

288n^ + 96n + 9 is divisible by 3

Answer 43

Oh don't ask why 3

Answer 44

Lucky guess? ;)

Answer 45

I'll give you my thought process, one moment

Answer 46

Because I think that if the problem was different, let's say that one of the primes that would be solution to such problem were higher, lets say 73. Then the attempt to solve with 3 would fail. :(

Answer 47

Few things to keep in mind before attempting the solution :
1) this is am academic problem. Not a Olympiad problem. So this is supposed to be easy and we shouldn't expect it to require a super computer or Einstein to solve this

Answer 48

Well, it's from a book that gives material to people who are going to participate in Olympiads. ;) (Though, it's very basic book)

Answer 49

2) if the common factor had been really 73, even Einstein couldn't have figured it out. This knowledge increases our confidence while solving homework problems

Answer 50

Ohk, you're preparing for Olympiads is it ?

Answer 51

Okay, I agree with this one ;) (Unless there would be an approach where an equation would be built. Perhaps it would be possible by looking at GCD? But I am going to agree with your statement that Einstein wouldn't solve it ;) )
Yes, I am ;)