# Without using prime factorization, find a prime factor of $\frac{(3^{41} -1)}{2}$

Not sure how to go about this. Law of quadratic reciprocity and Euler’s Criterion is recently learned material but I’m not sure how this applies.

#### Solutions Collecting From Web of "Without using prime factorization, find a prime factor of $\frac{(3^{41} -1)}{2}$"

Note that by a Legendre symbol calculation, we have $(3/83)=1$. Since $3$ is a quadratic residue of $83$, it follows that $3^{(83-1)/2}\equiv 1\pmod{83}$. So $83$ is a prime divisor of your number.

Alternately, you could use Euler’s Criterion to show that $3$ is a quadratic residue of $83$. That involves somewhat more calculation than the calculation of the Legendre symbol (but less theory).

One answer is 83, as found by Andre (sorry for the accent .. )

Here is a way to educatedly “guess” it: If $p = 41a+1$ is prime, then both $p$ and $3^{41}-1$ divide $3^{41a} -1= 3^{p-1}-1$. There is a chance that $p$ divides $3^{41}-1$. Since $a=1$ doesn’t work, the next to try is $a=2$. Then $(3^{41})^2 -1 = (3^{41}-1)(3^{41}+1)$ is a multiple of 83. As $3^4 \equiv -2 \pmod{83}$, it follows that $3^{40} \equiv 1024 \equiv 28 \pmod{83}$, hence $3^{41} \equiv 1 \pmod{83}$.

Remark:
Mathematica claims that the prime factorization of $3^{41}-1$ is $2\cdot 83\cdot 2526913\cdot 86950696619$. All three odd primes are $\equiv 1\pmod{41}$