# 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

-
Do you know that $(a,m)=1$ gives you some $r$ with the property that $ar\equiv 1 (\mod m)$? Use this by $a^k\equiv b^k$ means $ba^k\equiv b^{k+1}\equiv a^{k+1}$ Now multiply by $r^k$ to cancel the $a^k$ on both sides. – Matt Feb 24 '11 at 1:09
$\gcd(a,m)=1$ and the other two equations also implies $\gcd(b,m)=1$. Now subtract the two initial equations and cancel $a^k$ and $b^k$ (why?) to get $a-1 \equiv b-1 \bmod m$ – user17762 Feb 24 '11 at 1:14
@Matt: thanks for the property. – Chan Feb 24 '11 at 1:16
I would suggest to argue directly, using that $$a^{k+1}-b^{k+1}=a^{k+1}-a^kb+a^kb-b^{k+1}=a^k(a-b)+b(a^k-b^k).$$ We have that $m$ divides the left hand side, and the second term of the right hand side, and therefore it must divide the first term of the right hand side. But we also have that $m$ and $a$ have no common factors, and therefore $m$ and $a^k$ have no common factors. So $m$ must divide $a-b$. – Andrés E. Caicedo Feb 24 '11 at 1:22
@Andres Caicedo: Very cool algebraic proof ;) ! Love it. – Chan Feb 24 '11 at 4:29

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.

-
Thanks a lot for your hint! I was 99% close to this approach by assuming $m|\left(a^{k}+a^{k-1}\cdot b+\cdots + b^{k}\right)$, then factoring this term into the second one :(. – Chan Feb 24 '11 at 1:15
you can use \pmod like this: $x=5 \pmod{7}$ – Ross Millikan Feb 24 '11 at 1:22

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\ (mod\ m)$

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've used that unit $\rm\:a\ \Rightarrow\:$ unit $\rm\: b\$ since $\rm\:b|b^k|a^k\:$, and units are closed under products/divisors, i.e. $\rm\ x\ y\:$ 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\:$.

-
Thanks for an elegant solution. – Chan Feb 24 '11 at 7:48
Again, here, my answer showed how to find a solution based on what was already done. What he had already tried. I do not agree with abandoning the work done on a partial solution just because there is a prettier one. Both should be pursued to the end. (If possible) – Eric Naslund Feb 28 '11 at 16:10
@Eric: One of the most important things to learn from an elementary number theory course is how to reason equationally with congruences - in particular understanding how they are similar to integer equations and how they differ. Many obfuscated divisibility arguments are utterly trivial when viewed equationally in terms of congruences. This is a prototypical example of such. To succeed in number theory it is essential to learn how to think this way. – Bill Dubuque Feb 28 '11 at 16:18

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.

-
Thanks for the editing and a great hint. – Chan Feb 24 '11 at 1:17

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.

-
very clear step by step proof. Many thanks ;) – Chan Feb 24 '11 at 4:30
• $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:

1. you have an easy reference later on;
2. the paper is a good thing to stare at when you are stuck;
3. the physical act of writing down of what you know can trigger new inspirations and connections.
-