Prime factorization of $\frac{3^{41} -1}{2}$ How can  I determine all prime factor of  $\frac{3^{41} -1}{2}$ without doing prime factorizations.
Any help will be appreciated.
 A: Due to the particular form of that number, its prime factors are restricted to a very specific subset of the prime numbers. If $p>41$ and 
$$ 3^{41}\equiv 1\pmod{p},$$
it follows that the order of $3$ in $\mathbb{F}_p^*$ is exactly $41$, so $41\mid (p-1)$ by Lagrange's theorem, or:
$$ p\equiv 1\pmod{41}.$$
The first prime in such a subset is $p=83$. In such a case,
$$ 3^{41}\equiv 3^{\frac{p-1}{2}} \equiv \left(\frac{3}{p}\right) \equiv 1\pmod{p}$$
by quadratic reciprocity, since $83\equiv -1\pmod{4}$ gives $\left(\frac{-1}{83}\right)=-1$ and $89\equiv -1\pmod{3}$ gives $\left(\frac{-3}{83}\right)=-1$, so $\left(\frac{3}{83}\right)=1$. You may check that no prime in the interval $[2,41]$ is a divisor of $\frac{3^{41}-1}{2}$, hence $\frac{3^{41}-1}{2}$ is $83$ times the product of some (huge) primes $\equiv 1\pmod{41}$.
It won't be an easy problem in the general case. For instance, to test numbers of the form $2^p-1$ (or $\frac{3^p-1}{2}$ with $p\equiv\pm 5\pmod{12}$) for primality is actually the main way to generate colossal primes (like $\frac{3^7-1}{2}=1093$, that is not so huge but is a neat example). On the other hand, the same argument as above shows that for any prime $p$, there are infinite primes $\equiv 1\pmod{p}$.
