Finding prime factors of $2^{300} - 1$

Question

My initial approach to this problem was to use Fermat's Little Theorem:

We seek primes $p$ such that $2^{300} \equiv 1 \pmod{p}$. By Fermat's Little Theorem, if $a^{p-1} = 2^{300}$ for some prime $p$ and $a \in \mathbb{Z}$ such that $p \nmid a$, then $p$ is a prime factor of $2^{300} - 1$.

Instinctively, I set $a=2$. Now, if $p-1\,|\,300$ and $p \nmid a$, then $p$ is a factor. Using this method, I listed all the factors of 300, and found that the following primes divide $2^{300} - 1$:

p = 3, 5, 7, 11, 13, 31, 61, 101, 151.

However, when I checked for other primes using Wolfram Alpha, I found that $p = 41$ also a factor. Obviously, my method wouldn't work since $40 \nmid 300$. Is there some other method (besides guess and check) which would reveal these extra prime factors?

Answer 1

Yes. We know that $$2^n-1 \big| 2^m-1$$ whenever $n|m$. In particular, because $20|300$, $2^{20}-1$ divides $2^{300}-1$, and any prime that divides $2^{20}-1$ will thus also divide $2^{300}-1$.

Now, we have $41$ divides $2^{20}-1$. Can you show this?

Answer 2

$2^{300} \equiv 1 \bmod{p}$ implies $2^{d} \equiv 1 \bmod{p}$, where $d=\gcd(300,p-1)$. So you have to consider also the primes $p$ such that $p-1$ has a common factor with $300$ (larger than $2$). Hence $41$ is a possibility.

Another method that gives you at least some factors is a cyclotomic factorization: $$ x^{n}-1=\prod _{d\mid n}\Phi _{d}(x) $$ and so $$ x^{300}-1=(x - 1) (x + 1) (x^2 + 1) (x^2 - x + 1) (x^2 + x + 1) (x^4 - x^2 + 1) (x^4 - x^3 + x^2 - x + 1) (x^4 + x^3 + x^2 + x + 1) (x^8 - x^6 + x^4 - x^2 + 1) (x^8 - x^7 + x^5 - x^4 + x^3 - x + 1) (x^8 + x^7 - x^5 - x^4 - x^3 + x + 1) (x^{16} + x^{14} - x^{10} - x^8 - x^6 + x^2 + 1) (x^{20} - x^{15} + x^{10} - x^5 + 1) (x^{20} + x^{15} + x^{10} + x^5 + 1) (x^{40} - x^{30} + x^{20} - x^{10} + 1) (x^{40} - x^{35} + x^{25} - x^{20} + x^{15} - x^5 + 1) (x^{40} + x^{35} - x^{25} - x^{20} - x^{15} + x^5 + 1) (x^{80} + x^{70} - x^{50} - x^{40} - x^{30} + x^{10} + 1) $$ Setting $x=2$ gives $$ 2^{300}-1=1 \cdot 3 \cdot 5 \cdot 3 \cdot 7 \cdot 13 \cdot 11 \cdot 31 \cdot 205 \cdot 151 \cdot 331 \cdot 80581 \cdot 1016801 \cdot 1082401\cdots $$ which already gives you several primes and smaller factors that are easy to factor.

The full answer is $$ 2^{300}-1=3^2×5^3×7×11×13×31×41×61×101×151×251×331×601×1201×1321×1801×4051×8101×63901×100801×268501×10567201×13334701×1182468601×1133836730401 $$ but its unlikely to be easy to get by hand.