0
$\begingroup$

Consider the following theorem:

For any $a, b \in \mathbb{Z}^+$, there exist $m, n \in \mathbb{Z}$ such that $m > n$ and $a\ |\ b^m - b^n$.

What's the best way to prove it? I have an idea (and I know it's true because of that idea), but I don't know how rigorous it is to constitute a proof.

$\endgroup$
2
  • $\begingroup$ Probably should rule out $a=0$, since then $a=0$, %b=2$ is counterexample. $\endgroup$ Jul 12, 2013 at 14:48
  • $\begingroup$ Positive integers. Thanks again. $\endgroup$
    – Joe Z.
    Jul 12, 2013 at 14:49

1 Answer 1

9
$\begingroup$

Consider the remainders of $b^0$, $b^1$, $b^2$, ... when divided by $a$. Since this is an infinite sequence with finitely many possible values we must have $n$ and $m$ such that the remainder of the division of $b^n$ by $a$ is the same as the one of $b^m$. This is equivalent to $a|b^m-b^n$. In fact it is enough to consider $0\leq n,m\leq a$.

$\endgroup$
1
  • $\begingroup$ Haha, the method I was thinking of involved fractional representations in base $b$. Yours is much more elegant. $\endgroup$
    – Joe Z.
    Jul 12, 2013 at 14:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .