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

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?

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?

• Thanks, I didn't know that $n|m \implies 2^n-1 | 2^m - 1$. Also, I factored $2^{20}-1$ into $(2^{10}+1)(2^5+1)(2^5-1)$, and checked that $41|2^{10}+1$ by hand. There might be a more formal way of showing this, but I'm not too experienced in number theory.
– user736621
Commented May 21, 2020 at 23:17
• @aroe114: $2^n\equiv1\pmod{2^n-1},$ so if $m=kn$ then $2^m\equiv1\pmod{2^n-1}$. Also, using Euler's criterion, $2^{20}\equiv1\bmod41$ because $41\equiv1\bmod8$ Commented May 22, 2020 at 0:10

$$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.

• Thank you, that fact explains why I was missing some factors.
– user736621
Commented May 21, 2020 at 23:22