This is a question involving the use of the generalized pigeonhole principle.
Basically, here are the things that I know (but unsure whether they're relevant to the problem):
- Powers of $7$ are always odd. Hence, their differences are always even
- Their differences are always divisible by $7$.
Here's what I attempted to do:
Let $a = 7^x$ and $b = 7^y$, so $x = \log_7 a$ and $y = \log_7 b$:
$x\log_7 = \log a$
$y\log_7 = \log b$
$(a-b) \% k = 0$
I really have no idea how to set this up so I can use the generalized pigeonhole principle for this proof. I'm not even sure if I'm on the right track to solving this problem. Thanks for the help.
Best Answer
$k$ divides $7^x$ $-$ $7^y$ implies $7^x$ and $7^y$ leave the same remainder upon division by $k$. Assume to the contrary, that all powers of $7$ leave a different remainder upon division by $k$. Clearly, there are only $k$ possible remainders. Considering the numbers $7$, $7^2$, $7^3$ ,...., $7^{k+1}$, according to our assumption each of them leave a different remainder upon division by $k$. There are $k$ possible remainders (pidgeonholes) as mentioned earlier, but $k+1$ numbers(pidgeons), hence the pidgeon-hole principle forces a contradiction. Hence there are two $i$ , $j$ such that $7^i$, $7^j$ leave the same remainder upon division by $k$ and their difference is what we are looking for