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: Hint $\rm \ b^k \equiv a^k \Rightarrow\ b^{k+1} \equiv\: b\ a^k \equiv\: a^{k+1} \Rightarrow\ b\equiv a\ $ by cancelling $\rm\ a^k.\: $ Recall that if $\rm\ (a,m) = 1\ $ then $\rm\:a\:$ is invertible, so cancellable, $\!\rm\bmod  m,\,$ e.g. by Bezout.
Generally $\rm\,\color{#c00}{A\equiv B},\, aA\equiv b\color{#c00}B\,\Rightarrow\, aA\equiv b\color{#c00}A\,\Rightarrow\, a\equiv b\,$ if $\rm\,A\,$ is cancellable. OP is $\rm\,A,B = a^k,b^k$ 
The same proof works in any ring where $\rm\:a\:$ is a unit, i.e. invertible. The proof cancels the units $\rm\ a^k = b^k\ $ from both sides of $\rm\ a^{k+1} = b^{k+1}\ $ to obtain $\rm\ a = b\:.\:$ Here we used that unit $\rm\:a\ \Rightarrow\: $ unit $\rm\: b\ $ by $\rm\:b\mid b^k\mid a^k,\,$ and units are closed under products/divisors: $\rm\ xy\:$ unit $\rm\iff\ x\:$ unit and $\rm\:y\:$ unit.
It's clearer dehomogenized using $\rm\ c = b/a\:,\: $ viz. $\rm\ 1 = c^k\ \Rightarrow\ c = c^{k+1} = 1\:$.
A: Here is the idea:  Show that (2) is impossible.  Suppose that $$m|\left( a^{k-1}+a^{k-2}\cdot b+\cdots + b^{k-1}\right)$$ and 
$$m|\left(a^{k}+a^{k-1}\cdot b+\cdots + b^{k}\right)$$
Then subtract $b$ times the first integer from the second integer.  That is consider $$\left( a^{k}+a^{k-1}\cdot b+\cdots + b^{k} \right) -b\cdot \left( a^{k-1}+a^{k-2}\cdot b+\cdots + b^{k-1} \right)= a^k$$
It then follows that $m$ divides $a^k$, but that is impossible.  (why?)
Hope that helps.
A: We have $$m|(a^{k}+a^{k-1}b+a^{k-2}b^2 + \cdots + ab^{k-1}+b^k)$$ $$-t(a^{k-1}+a^{k-2}b+a^{k-3}b^2+ \cdots + ab^{k-2} + b^{k-1}) = a^k$$ 
which is impossible.
A: This is related to what Bill Dubuque said but is more elementary:
Since $a^k = b^k$ mod $m$, one has $m | (a^k - b^k)$, and similarly $m | (a^{k+1} - b^{k+1})$. Thus by the first equation $m$ divides $b(a^k - b^k) = (a^kb - b^{k+1})$. Subtracting, we have that $m | (a^{k+1} - b^{k+1}) - (a^kb - b^{k+1}) = a^{k+1} - a^kb = a^k(a - b)$. But since $(a,m) = 1$, the fact that $m | a^k(a - b)$ means $m | a - b$, or equivalently $a = b$ mod $m$ which is what you needed to show. 
A: *

*$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.

