# Primality testing based on algebra — RMO training

Use some algebraic factorization techniques to prove the following classic gems of number theory:

1. Given two integers a and m larger than 1, show that, if m is odd, then $a+1$ is a divisor of $a^{m}+1$. Use this result to obtain the factorization of 1001.
2. Generalize, the above result  to  obtain that if  a and m are two integers larger than 1 and if $d \geq 1$ is an odd divisor of m, then $a^{m/d}+1$ is a divisor of $a^{m}+1$. use this result to show that 101 is a factor of 1000001.
3. Show that 7, 11, and 13 are factors of $10^{15}+1$
4. Show that $n^{4}+4$ is  a composite number for each integer $n \geq 2$. More generally, show that if a is a positive integer such that $2n$ is a perfect square, then $n^{4}+a^{2}$ is a composite number provided that $n \geq \sqrt{2a}$.

More later,

Nalin Pithwa

This site uses Akismet to reduce spam. Learn how your comment data is processed.