Skip to main content.

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 am − 1 and an + 1?


Let d be a common divisor (not necessarily the greatest) of am − 1 and an + 1.
Then there are integers r and s such that am − 1 = rd, and an + 1 = sd.
That is, am = rd + 1, and an = 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 (am)n = (an)m = amn.
Hence (u − t)d = 2.
Therefore d = 1 or d = 2.

Now, am − 1 and an + 1 are both even when a is odd, and both odd when a is even.

Therefore the greatest common divisor of am − 1 and an + 1 is:

Source: Original

Back to top