Solution to puzzle 51: Greatest common divisor

Let a, m, and n be positive integers, with a > 1, and m odd.
What is the greatest common divisor of a^m − 1 and aⁿ + 1?

---

Let d be a common divisor (not necessarily the greatest) of a^m − 1 and aⁿ + 1.
Then there are integers r and s such that a^m − 1 = rd, and aⁿ + 1 = sd.
That is, a^m = rd + 1, and aⁿ = sd − 1.

Then (am)n	= (rd + 1)n.
	= td + 1, for some integer, t.  (By the binomial theorem.)
And (an)m	= (sd − 1)m.
	= ud − 1, for some integer, u, since m is odd.

But (a^m)ⁿ = (aⁿ)^m = a^mn.
Hence (u − t)d = 2.
Therefore d = 1 or d = 2.

Now, a^m − 1 and aⁿ + 1 are both even when a is odd, and both odd when a is even.

Therefore the greatest common divisor of a^m − 1 and aⁿ + 1 is:

• 2, when a is odd,
• 1, when a is even.

Source: Original

Back to top