Prime Factorization of Large Numbers

Question

Recently, I have been required to compute the Prime Factorization of large numbers.

For instance,

$5^9 -1 $

I know that it ends in a $4$, so can be divided by $2$. Then can be divided by $2$ again, but this creates a factor tree which is what I am looking to avoid.

How would I go about prime factorising this?

---

By my factor tree method I get to $2\times 2\times 19\times 31\times 829$. But I had to type into the internet whether $829$ was a prime, so I immediately run into a problem.

Any help or ideas would be appreciated!

Answer 1

What you are attempting to do is called prime factorization (Yes, that is in the title).

In order to determine if $829$ is a prime number or not, I would use trial division:

If the number $829$ is not divisible by any prime number that is less that $\sqrt{829}$ than the number $829$ is prime.

By using your factor tree method, you have factored it to $2\times 2\times 19\times 31\times 829$.

At this point, if you are doing it right (test the divisibility of $5^9-1$ starting from the smallest prime number, which is $2$), then the number $829$ is not divisible by any prime numbers from $2$ to $31$. Because $31^2=961>829$, that is enough to show that $829$ is a prime number.

Answer 2

no truly simple way. You have $$ x^9 - 1 = (x-1)(x^2 + x + 1)(x^6 + x^3 + 1) $$ As the third factor is also of the form $u^2 + u + 1,$ it can only be divisible by primes $p \equiv 1 \pmod 3 \; ,$ more specifically $p \equiv 7 \pmod 6 \; .$ Once you get to $15751$ and find that it is not divisible by $7,13,$ you get a bit of luck with $19.$ The leftover is $829.$ It is not divisible by $19$ or $31,$ and that is it. You have exceeded $\sqrt {829} \approx 28.7$ so $829$ is prime.

In case of interest, this has to do with quadratic residues.