Manipulation of Large Numbers

Question

I encountered a puzzling problem (though I don't remember where) to find the prime factorization of the number $$7^{100}-1$$ I think there may be some kind of trick or technique that one could use to solve this problem that I am unaware of. I already know the fact that any number of the form $c^n-1$ is divisible by $c-1$, so I know that $7^{100}-1$ is divisible by $6$, but now what do I do?

Answer 1

Take advantage of the difference of two squares:

$$\begin{align}7^{100}-1&=(7^{50}+1)(7^{50}-1)\\&=(7^{50}+1)(7^{25}+1)(7^{25}-1)\end{align}$$

Then recall $a^5-b^5=(a-b)(a^4+a^3b+a^2b^2+ab^3+b^4)$ to get

$$\begin{align}7^{25}-1&=(7^5-1)(7^{20}+7^{15}+7^{10}+7^5+1)\\&=(7-1)(7^4+7^3+7^2+7+1)(7^{20}+7^{15}+7^{10}+7^5+1)\end{align}$$

Likewise, $a^5+b^5=(a+b)(a^4-a^3b+a^2b^2-ab^3+b^4)$, so we have

$$\begin{align}7^{25}+1&=(7^5+1)(7^{20}-7^{15}+7^{10}-7^5+1)\\&=(7+1)(7^4-7^3+7^2-7+1)(7^{20}-7^{15}+7^{10}-7^5+1)\\7^{50}+1&=(7^{10}+1)(7^{40}-7^{30}+7^{20}-7^{10}+1)\\&=(7^2+1)(7^8-7^6+7^4-7^2+1)(7^{40}-7^{30}+7^{20}-7^{10}+1)\end{align}$$

We see that

$7-1=6=2\times3$

$7^4+7^3+7^2+7+1=2801=\text{prime}$

$7^{20}+7^{15}+7^{10}+7^5+1=79797014141614001=2551\times31280679788951$

$7+1=8=2^3$

$7^4-7^3+7^2-7+1=2101=11\times191$

$7^{20}-7^{15}+7^{10}-7^5+1=79787519018560501=\text{prime}$

$7^2+1=50=2\times5^2$

$7^8-7^6+7^4-7^2+1=5649505=5\times281\times4021$

$7^{40}-7^{30}+7^{20}-7^{10}+1\\=6366805738369687774841443066497505\\=5\times101\times13001\times25301\times38327966300231909291101$

Answer 2

You can find a number of small factors fairly easily. As you say, $6$ is a factor. You can also factor it as the difference of squares. One of those factors will again factor as the difference of squares. This brings you to $7^{25}+1$ which has a factor $7+1$. The difference of fifth powers factors as well. I doubt you will get the complete factorization, which Alpha says is $2^5\times 3\times 5^4\times 11\times 101\times 191\times 281\times 2551\times 2801\times 4021\times 13001\times 25301\times 31280679788951\times 79787519018560501\times 38327966300231909291101$

Answer 3

As suggested in the comments, start from the factorization of $x^{100}-1$ in terms of cyclotomic polynomials: $$ x^{100}-1= (x - 1) (x + 1) (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^{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) $$ which comes from $$ x^n-1=\prod_{d \mid n} \Phi_d(x) $$

This gives $$ 7^{100}-1 = 6 \cdot 8\cdot 50\cdot 2101\cdot 2801\cdot 5649505\cdot 79787519018560501\cdot 79797014141614001\cdot 6366805738369687774841443066497505 $$ It is possible to further factorize this, but it is not easy because $79787519018560501$ is prime and $6366805738369687774841443066497505$ has a prime factor $38327966300231909291101$, though its other factors are quite small.

factor from BSD gives

6: 2 3
8: 2 2 2
50: 2 5 5
2101: 11 191
2801: 2801
5649505: 5 281 4021
79787519018560501: 79787519018560501
79797014141614001: 2551 31280679788951
6366805738369687774841443066497505: 5 101 13001 25301 38327966300231909291101