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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s