Find p

Number Theory Level 5

Find the smallest (positive) prime $p$ , such that for some integer $n$ , $p\mid{58n^2+1}$

The answer is 31.

3 solutions

Pebrudal Zanu
Jan 11, 2014

This is my solution using python:

 def check(p):

for i in range (1,p+1):

 if (58*i**2+1)%p==0:

 print i

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=31$

It's clear that $p$ is not $2$ or $29$ . So let's assume $p$ is an odd prime not equal to $29$ . $p | 58n^2+1$ iff $p | (58n)^2+58$ iff $(58n)^2\equiv -58\bmod p$ iff $\bigl(\frac{-58}{p}\bigr) = 1$ iff $\bigl(\frac{-2}{p}\bigr) = \bigl(\frac{29}{p}\bigr)=\bigl(\frac{p}{29}\bigr)$ .

By listing $k^2\bmod 29$ for $1\le k \le 14$ , it's easy to see that if $p<29$ , then $\bigl(\frac{p}{29}\bigr)=1$ iff $p=5,7,13,23$ . But $\bigl(\frac{-2}{p}\bigr)=1$ iff $p\equiv 1,3\bmod 8$ Hence there is no odd prime $p<29$ such that $\bigl(\frac{-2}{p}\bigr) =\bigl(\frac{p}{29}\bigr)$ .

If $p=31$ , then $\bigl(\frac{p}{29}\bigr) = \bigl(\frac{2}{29}\bigr)=-1$ and $\bigl(\frac{-2}{p}\bigr) = -1$ . Therefore $p=31$ is the smallest prime such that $p | 58n^2+1$ for some $n$ .

George G - 7 years, 5 months ago

Can you explain the step why -58/p =1? And also the next equality...

Eddie The Head - 7 years, 5 months ago

Google quadratic residues, everything you need to know about quadratic residues is here.

George G - 7 years, 5 months ago

@George G – Oh..I had heard about quadratic reciprocity but never studied them in detail...maybe I should...thanks....

Eddie The Head - 7 years, 5 months ago

@George G – Maybe someone could write an introductory post on Quadratic Residues ? :)

Happy Melodies - 7 years, 5 months ago

Very nice, George G.

Peter Byers - 7 years, 5 months ago

Well of course you can easily write a program to check cases.. but what's the point?

Ben Frankel - 7 years, 5 months ago

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.

pebrudal zanu - 7 years, 5 months ago

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.

Ben Frankel - 7 years, 5 months ago

@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

pebrudal zanu - 7 years, 5 months ago

There is no need to check for 2 as $p$ cannot be even.

Keshav Kumar - 7 years, 5 months ago

Shashank Sharma
Apr 11, 2014

I'm not able to prove how p=31 is minimal but this is how I approached

$58 n^{2} + 1 + 31n - 31n = p * k$

$(29n+1)(2n+1) - 31n = 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?

Jayakumar Krishnan - 7 years, 1 month ago

Allen Yang
Jan 13, 2014

use Euler's criterion to bash out quadratic residues

Find p

The answer is 31.

3 solutions

0 pending reports

Related quizzes

Quadratic Residues - Primes