How to show two different positive powers of $5$ that differ by a multiple of $123$ (Pigeon-hole Principle)

Question

I am not sure how to really approach this problem:

Show that there are two different positive powers of $5$ $($in other words, $5^{n}$, for $n$ $\in$ $\mathbb{Z^{+}}$), that differ by a multiple of $123$.

Again... I am not sure how to proceed. I have labored over this problem for quite a bit now.

Should I be using a proof technique other than a direct one?

Should I be using a proof at all since this seemingly concerns existence?

Should I just somehow try to guess two numbers that work?

---

Additionally, are they asking for some quantity $c$ $=$ $(5^{n})$ $-$ $(5^{k})$ where $n$ , $k$ $\in$ $\mathbb{Z^{+}}$ and $n$ $\neq$ $k$ , such that $123$ $\mid$ $c$ ?

I am not even certain what they are asking for, so I am faced with much difficulty.

I would appreciate hints in the right direction and any input you might have.

Answer 1

5 is coprime to 123, so the powers of 5 must lie in 122 distinct residue classes modulo 123. Now consider any 123 admissible powers; by the pigeonhole principle there must be two different powers with the same residue class, corresponding to their difference being a multiple of 123.

Explicitly, Euler's theorem gives $$5^{\varphi(123)}=5^{80}\equiv1\bmod123$$ This immediately gives $123\mid5^{160}-5^{80}$.

Answer 2

For a pigeonhole principle proof, consider the $124$ numbers $5,5^2,\ldots,5^{124}$ or rather their remainders under division by $123$. There are only $123$ possible such remainders, so that there are $i$, $j$ with $1\le i<j\le 124$ such that $5^i$ and $5^j$ have the same remainder under division by $123$, that is $5^i\equiv 5^j\pmod{123}$.