Primality testing based on algebra — RMO training | For the love of Maths: the Queen of all Sciences

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

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.
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.
Show that 7, 11, and 13 are factors of $10^{15}+1$
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}$ .