Prove that if $a^{k} \equiv b^{k}  \pmod m $ and $a^{k+1} \equiv b^{k+1}  \pmod m $ and $\gcd( a, m ) = 1$ then $a \equiv b \pmod m $ My attempt:
Since $a^{k} \equiv b^{k}( \text{mod}\ \ m ) \implies m|( a^{k} - b^{k} )$ and $a^{k+1} \equiv b^{k+1}( \text{mod}\ \ m ) \implies m|( a^{k+1} - b^{k+1} ) $
Using binomial identity, we have:
$$a^{k} - b^{k} = ( a - b )( a^{k - 1} + a^{k - 2}b + a^{k - 3}b + ... ab^{k - 2} + b^{k - 1} )$$
$$a^{k + 1} - b^{k + 1} = ( a - b )( a^{k} + a^{k - 1}b + a^{k - 2}b + ... ab^{k - 1} + b^{k} )$$
Now there are two cases:
1. If $m|(a - b)$, we're done.
2. Else $m|( a^{k - 1} + a^{k - 2}b + a^{k - 3}b + ... ab^{k - 2} + b^{k - 1} )$ and $m|( a^{k} + a^{k - 1}b + a^{k - 2}b + ... ab^{k - 1} + b^{k} )$
And I was stuck from here, since I could not deduce anything from these two observations. I still have $(a, m) = 1$, and I guess this condition is used to prevent $m$ divides by the two right hand side above.   
A hint would be greatly appreciated.   
Thanks,
Chan

*

*$a\equiv b\pmod{n} \quad\textrm{and}\quad b\equiv c\pmod{n}\Rightarrow a\equiv c\pmod{n}$

*$a\equiv b\pmod{n}\Leftrightarrow b\equiv a\pmod{n}$

*$a\equiv b\pmod{n}\Rightarrow ac\equiv bc\pmod{n}$ for any $c$ 
The list can be enough to get $$a^kb\equiv a^ka\pmod{m}.$$
I would like to mentioned a theorem I just learned from Hardy's An Introduction to the Theory of Numbers:

THEOREM 54. If $(k, m) = d$, then
  $$kx\equiv ky\pmod{m}\Rightarrow x\equiv y\pmod{\frac{m}{d}},$$
  and conversely.

This theorem tells you that when and how you can "cancel" something in the congruence equation. Now it suffices to show that $(a^k,m)=1$, which can be done by reductio ad absurdum (proof by contradiction).

When one solves some problem about congruence, he/she had better have a list of the properties of congruence in hand or at least in mind. This is convenient for your thinking. As Terence Tao said in his "Solving Mathematical Problems", putting everything down on paper helps in three ways:


*

*you have an easy reference later
on;

*the paper is a good thing to
stare at when you are stuck;

*the physical act of writing down
of what you know can trigger new
inspirations and connections.

