Recall: for some
For the inductive step, we assume that it is true for some , i.e and we want to prove that it is also true for .
Multiply both sides by and substitute for some integer (just go by the definition of congruences!)
Okay, so I understand that I must show that a^(k+1) and b^(k+1) are congruent mod m.
And I understand that a and b are congruent mod m iff a = b + km, k e Z.
But, Im not sure why I would multiply both sides by a?? And where do I plug in my Inductive Hyp? Is the base case 0?
edit: Sorry, I just noticed you are required to use induction. Too bad!
I don't think it is necessary to use induction.
If a and b are congruent modulo n, then a-b is a multiple of n.
For any positive integer n, .
Do you see how that shows that is a multiple of n?