Given $N=2^{29}+1$, we want to find two different prime factors of $N$.
Now, we have $2^{29}+1\equiv (-1)^{29}+1\equiv0\pmod 3$, hence $3\mid N$.
Next, we have
$$N=2^{29}+1\equiv 2(2^7)^4+1\equiv 2(2\cdot 59+10)^4+1\equiv 2\cdot 10^4+1\pmod {59}$$
$$N\equiv 2(-18)^2+1\equiv 648+1=11\cdot 59\equiv 0\pmod{59},$$ so that $59\mid N$.
I already proved that if $p$ is a prime with $p\mid N$, then $p=3$ or $p=58k+1$ for some $k$; that's where the guess to choose $59$ came from.
Is there a more elegant way to show that $59\mid N$?
I was thinking of using Fermat's little theorem together with the fact that $2^{58}-1=(2^{29}+1)(2^{29}-1)$, but I'm unable to prove that $\gcd(2^{29}-1,59)=1$.
Find two different prime factors of $2^{29}+1$
elementary-number-theory
Best Answer
By Euler's criterion, $2^{29}\equiv\left(\dfrac2{59}\right)\bmod59$.
There is no need to compute all thirty quadratic residues $\bmod 59$.
We can know that $\left(\dfrac2{59}\right)=-1$ from the Second Supplement to Quadratic Reciprocity;
cf. here and here.