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

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.

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}$.

• I don't really approve of the change of tags here. It is an inclusion-exclusion problem from a discrete math class. Not a number theory course where modulus arithmetic is overly used. Euler's theorem has not been introduced to the rest of the class, so while beautiful, it is not useful for the purposes of this question. – Prime Jul 11 '18 at 6:05
• I did use a rollback here. Those tags are important and the questions that I did ask are important motivations for the question. – Prime Jul 11 '18 at 6:06
• @Prime You cannot use inclusion/exclusion for such a problem. Rather... – Parcly Taxel Jul 11 '18 at 6:07
• Looks like a pigeonhole principle question not an inclusion-exclusion question. – Lord Shark the Unknown Jul 11 '18 at 6:10
• @Prime I just gave you that. – Parcly Taxel Jul 11 '18 at 6:14

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}$.

• So we are not including $5$ or $5^{124}$, right? – Prime Jul 11 '18 at 6:18
• With $i$ and $j$, I am assuming WLOG, correct? – Prime Jul 11 '18 at 6:23