Proof on Congruences

[davect]

*notation \(\displaystyle |\) is divisibility
*notation \(\displaystyle \equiv\) is congruent
Problem: Show that if \(\displaystyle a^k \equiv b^k(mod\,m)\) and \(\displaystyle a^{k+1} \equiv b^{k+1} (mod \, m)\), where a, b, k, and m are integers with k > 0 and m > 0 such that gcd(a,m) = 1, then \(\displaystyle a \equiv b (mod \, m).\)

I really don't know how to approach this problem. I think I need to somehow come to the conclusion that either
\(\displaystyle (a^k - b^k) | (a - b)\) or \(\displaystyle (a^{k+1} - b^{k+1}) | (a - b)\),
and because \(\displaystyle m | (a^k - b^k)\) and \(\displaystyle m | (a^{k+1} - b^{k+1})\)
that way I would be able to say that \(\displaystyle m | (a - b)\),
therefore \(\displaystyle a \equiv b (mod \, m)\).

but I don't know how to get to the conclusion that either \(\displaystyle (a^k - b^k) | (a - b)\) or \(\displaystyle (a^{k+1} - b^{k+1}) | (a - b)\).
Thanks for any help, and if need be, I will try to clarify my question

 

[davect]

I've recently worked more on this problem, and I was hoping if anyone could tell me if this is correct:

Since \(\displaystyle a^k \equiv b^k (mod \, m)\) => \(\displaystyle a^k = b^k + l*m\) then \(\displaystyle l*m = a^k - b ^k\)
and \(\displaystyle a^{k+1} \equiv b^{k+1} (mod \, m)\) => \(\displaystyle a^{k+1} = b^{k+1} + n *m\) then \(\displaystyle n*m = a^{k+1} - b^{k+1}\)
then,
\(\displaystyle (a^{k+1} - a^k) - (b^{k+1} - b^k) = (a^{k+1} - b^{k+1}) - (a^k - b^k) = n*m - l*m = m(n - l)\)
thus,
\(\displaystyle m | [(a^{k+1} - a^k) - (b^{k+1} - b^k)]\)
and because \(\displaystyle (a^{k+1} - a^k) - (b^{k+1} - b^k) = (a^k)(a-1) - (b^k)(b-1)\)
then \(\displaystyle (a^k)(a-1) \equiv (b^k)(b-1) (mod \, m)\)

Here is where I am uncertain I can say this:
then \(\displaystyle a^k \equiv b^k (mod\, m)\) and \(\displaystyle (a-1) \equiv (b-1) (mod\, m)\) => \(\displaystyle m | [(a-1) - (b-1)] <=> m | (a-b)\)
hence \(\displaystyle a \equiv b (mod\, m)\)

 

[daon]

Here is where I am uncertain I can say this:
then \(\displaystyle a^k \equiv b^k (mod\, m)\) and \(\displaystyle (a-1) \equiv (b-1) (mod\, m)\) => \(\displaystyle m | [(a-1) - (b-1)] <=> m | (a-b)\)
hence \(\displaystyle a \equiv b (mod\, m)\)

You cannot deduce that (a-1)=(b-1) (mod m) from that statement. You essentially divided by a^k, which is only valid if gcd(a,m)=1.

i.e., if a^k=b^k then b^k(b-1) = a^k(b-1) <=> m| a^k(b-1)-a^k(a-1) <=> m|a^k(b-a). If gcd(a,m)=1 you have your result, but otherwise you can't conclude m|(b-a).

It looks like you're close. I would try induction, though.

 

[davect]

Ok in the problem it does state that the \(\displaystyle gcd(a, m) = 1\), but how can you say that \(\displaystyle a^k = b ^k\) from it saying that the \(\displaystyle gcd(a, m) = 1\)?

I assume it would also have to do with \(\displaystyle a^k \equiv b^k (mod \, m)\) and I see that \(\displaystyle a^k = b^k + l*m\),

but does \(\displaystyle gcd(a, m) = 1\) make the \(\displaystyle l*m\) disappear?

The only thing I get from seeing \(\displaystyle gcd(a, m) = 1\) is that there is a linear combination such that \(\displaystyle xa + ym = 1\).

 

[daon]

if gcd(a,m) is 1 then the prime factorization of a contains none of the prime factors of that of m. Hence, neither will a^k, m. Since none of the factors of a^k divide m, they must all divide (a-b).