8
$\begingroup$

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

  • 0
    Maybe you could treat it as$a$problem in the multiplicative group modulo m, which makes things easier. Thanks.2011-02-24

5 Answers 5

1
  • $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.
6

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\:$.

  • 1
    @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.2011-02-28
4

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.

  • 1
    you can use \pmod like this: $x=5 \pmod{7}$2011-02-24
2

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.

  • 0
    Thanks for the editing and a great hint.2011-02-24
2

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.

  • 0
    very clear step by step proof. Many thanks ;)2011-02-24