Prove that if $a^{170} ≡ 1 \text{ (mod n) and }a^{111} ≡ 1 \text{ (mod n)} \text{ then } a ≡ 1 \text{ (mod n)}$ Let n and a be positive integers. Prove that if 
$a^{170} ≡ 1 \text{ (mod n) and }a^{111} ≡ 1 \text{ (mod n)} \text{ then } a ≡ 1 \text{ (mod n)}$
I know that if $a ≡ 1 \text{ (mod n)}$ then $a^{170} ≡ 1 \text{ (mod n)}$ and  $a^{111} ≡ 1 \text{ (mod n)}$, but I am not sure how I can show this in the opposite direction.
 A: Here is a hint:
$32\times170-49\times111=1$
A: $ a^{\large \color{#c00}1}\! \equiv 1,\,$ by $\,a\,$ has order $\,\color{#c00}{k\!=\!1},\,$ by $\,k\,$ divides coprimes $170,111,\,$ by the Order Theorem.
Remark $\ $ This is a multiplicative analog of the well-known fact that a fraction writable with coprime denominators is an integer (by its least denominator ("order") divides coprimes so it must be $\color{#c00}1).\,$ See here for further discussion of this analogy (and denominator and order ideal generalizations). 
A: You can indirectly use the Euclidean algorithm on the exponents to derive the result, as follows:


*

*$a^{170} = a^{111}\cdot a^{59} \equiv 1$, and $a^{111} \equiv 1$. Thus, $a^{59} \equiv 1$.

*$a^{111} = a^{59}\cdot a^{52} \equiv 1$, and $a^{59} \equiv 1$. Thus, $a^{52} \equiv 1$.

*$a^{59} = a^{52}\cdot a^{7} \equiv 1$, and $a^{52} \equiv 1$. Thus, $a^{7} \equiv 1$.

*$a^{52} = (a^{7})^{7}\cdot a^{3} \equiv 1$, and $a^{7} \equiv 1$. Thus, $a^{3} \equiv 1$.

*$a^{7} = (a^{3})^{2}\cdot a^{1} \equiv 1$, and $a^{3} \equiv 1$. Thus, $a^{1} = a \equiv 1$.


Applying this concept in general leads to the theorem
$$a^x \equiv a^y \equiv 1\quad(\text{mod } n)\quad\implies\quad a^{\mathrm{gcd}(x,y)} \equiv 1\quad(\text{mod }n).$$
A: $1 \equiv  a^{170}=a^{111}a^{59}\equiv 1*a^{59}\equiv a^{59}\pmod n$.
And $1 \equiv a^{111}= a^{59}a^{52}\equiv 1a^{52}\equiv a^{52}\pmod n$ and .... keep going....
This is akin to using Euclid's algarithm to show $\gcd(111,170) = 1$.
....
$1 \equiv a^{59} = a^{52}a^{7}\equiv 1*a^7\equiv a^7\pmod n$.
$1 \equiv a^{52}\equiv (a^7)^7a^3 \equiv 1^7a^3\equiv a^3 \pmod n$
$1 \equiv a^7 \equiv (a^3)^2*a \equiv 1^2a \equiv a \pmod n$. 
That's that.
Alternatively we can use EA and Bezouts lemma to show that 
$1 = 7- 2*3 = 7- 2(52- 7*7)$
$= 15*7 - 2*52 = 15*(59-52)- 2*52 = 15*59 - 17*52=$
$=15*59- 17(111-59) = 32*59 - 17*111 =$
$ 32*(170-111) - 17*111=32*170 - 49*111$
So $5440 = 32*170$ and $5540= 5439+1 = 49*111 + 1$.
And so....
So $a^{5440}=(a^{170})^{32} \equiv 1^{32} \equiv 1 \pmod n$.
But also $a^{5440}= a*a^{5439}=a*(a^{111})^{49}\equiv a*1^{49}\equiv a \pmod n$.
So transitively, $a\equiv a^{5440}\equiv 1 \pmod{n}$.
A: Since $170$ and $111$ are relatively prime, there exist, by Bezout's theorem, $x,y$ such that $x170+y111=1$.  But then $1\cong {(a^{170})}^x\cdot {(a^{111})}^y\cong a^{x170+y111}\cong a\pmod n$.
Of course, this generalises to any coprime exponents.
