Solutions to primality testing based on algebra — RMO training

Problem 1:

Given two integers a and m larger than 1, show that, if m is odd, then n+1 then a+1 is a divisor of a^{m}+1. Use this result to obtain the factorization of 1001.

Solution 1:

Since m is odd, we have a^{m}+1 = (a+1)(a^{m-1}-a^{m-2}+a^{m-3}- \ldots a+1) and the result follows.

This shows that

1001 = 10^{3}+1 = (10+1)(10^{2}-10+1)=11.91=11.7.13.

Problem 2:

Generalize the result of the above problem 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.

 Solution 2:

The result is immediate if we write a^{m}+1=(a^{m/d})^{d}+1 and then we apply the result of the above problem. This shows that

1000001 = 10^{6}+1 = (10^{2}+1)(10^{4}-10^{2}+1)=101.9901.

Problem 3:

Show that 7, 11 and 13 are factors of 10^{15}+1

Solution 3:

It follows from the previous result that 10^{15}+1 = (10^{3}+1)((10^{3})^{4}-(10^{3})^{3}+(10^{3})^{2}-10^{3}+1).

The result then follows from the fact that 7, 11, and 13 factors of 1001.

Problem 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 2a is a perfect square, then n^{4}+a^{2} is a composite number provided that n \geq \sqrt{2a}

 Solution 4:

It is enough to observe that n^{4}+4= (n^{2}-2n+2)(n^{2}+2n+2). For the general case, we only need to observe that n^{4}+a^{2}= (n^{2}-\sqrt{2a}n +a)(n^{2}+\sqrt{2a}n+a).

We also make an observation that the condition n \geq \sqrt{2a} is sufficient but not necessary.


Nalin Pithwa


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

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