Find the smallest (positive) prime p , such that for some integer n , p ∣ 5 8 n 2 + 1
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
It's clear that p is not 2 or 2 9 . So let's assume p is an odd prime not equal to 2 9 . p ∣ 5 8 n 2 + 1 iff p ∣ ( 5 8 n ) 2 + 5 8 iff ( 5 8 n ) 2 ≡ − 5 8 m o d p iff ( p − 5 8 ) = 1 iff ( p − 2 ) = ( p 2 9 ) = ( 2 9 p ) .
By listing k 2 m o d 2 9 for 1 ≤ k ≤ 1 4 , it's easy to see that if p < 2 9 , then ( 2 9 p ) = 1 iff p = 5 , 7 , 1 3 , 2 3 . But ( p − 2 ) = 1 iff p ≡ 1 , 3 m o d 8 Hence there is no odd prime p < 2 9 such that ( p − 2 ) = ( 2 9 p ) .
If p = 3 1 , then ( 2 9 p ) = ( 2 9 2 ) = − 1 and ( p − 2 ) = − 1 . Therefore p = 3 1 is the smallest prime such that p ∣ 5 8 n 2 + 1 for some n .
Log in to reply
Can you explain the step why -58/p =1? And also the next equality...
Log in to reply
Log in to reply
@George G – Oh..I had heard about quadratic reciprocity but never studied them in detail...maybe I should...thanks....
@George G – Maybe someone could write an introductory post on Quadratic Residues ? :)
Very nice, George G.
Well of course you can easily write a program to check cases.. but what's the point?
Log in to reply
If we check one by one need much time for solve this problem
Specifically:
p=2:
58*1^2 + 1 mod p is not 0.
So p=2 does not work.
p=3:
58*1^2 + 1 mod p is not 0.
58*2^2 + 1 mod p is not 0.
So p=3 does not work.
p=5:
58*1^2 + 1 mod p is not 0.
58*2^2 + 1 mod p is not 0.
58*3^2 + 1 mod p is not 0.
58*4^2 + 1 mod p is not 0.
So p=5 does not work.
So on.
Log in to reply
No, I understand how the program works, and it truly does get the correct answer. I just think that brute force with the help of a computer is not the point of this question.
This doesn't seem like a Computer Science question, in which case writing a program is very often the expected method of solution.
Log in to reply
@Ben Frankel – Thank you for your advice... I try to solve this problem with CS only for practice. Because I am beginner in programming... Next time, I will try solve CS problem in brilliant to practice problem... :D
There is no need to check for 2 as p cannot be even.
I'm not able to prove how p=31 is minimal but this is how I approached
5 8 n 2 + 1 + 3 1 n − 3 1 n = p ∗ k
( 2 9 n + 1 ) ( 2 n + 1 ) − 3 1 n = p ∗ k
Hence we see that p has to be 31 to divide the equation on left
But why do you have to take it as only 31 n?
use Euler's criterion to bash out quadratic residues
Problem Loading...
Note Loading...
Set Loading...
This is my solution using python:
When we check n=2,3,5,7,11,13,17,19,23,29, we don't get value of i. But when p=31, we get i=16 and 15. So the answer p = 3 1