Maths Olympiad Prep

Library / /152 of 520

Number theory Difficulty 5.8 AIME, harder Prove it

26 Let a,m,na, m, n be positive integers, a>1a>1. Prove: (am−1,an−1)=a(m,n)−1\left(a^{m}-1, a^{n}-1\right)=a^{(m, n)}-1.

Solution

26. Suppose m>nm>n, then
and
(am−1,an−1)=(am−an,an−1)=(an(am−n−1),an−1),(an,an−1)=1,(am−1,an−1)=(am−n−1,an−1),\begin{array}{l} \left(a^{m}-1, a^{n}-1\right)=\left(a^{m}-a^{n}, a^{n}-1\right) \\ =\left(a^{n}\left(a^{m-n}-1\right), a^{n}-1\right), \\ \left(a^{n}, a^{n}-1\right)=1, \\ \left(a^{m}-1, a^{n}-1\right)=\left(a^{m-n}-1, a^{n}-1\right), \end{array}

By repeatedly applying this, performing the "Euclidean algorithm" on the exponents, we can see that the conclusion holds.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.