Hi I've been trying to solve this problem for at least 2 hours now but I can't figure it out. If anyone can help I would really appreciate it!
I am asked to prove this question using Mathematical Inductions by applying Pigeonhole Principle.
"Prove that there exists a positive integer n such that m divides $2^n$-1 "
I took base condition as n=1,for which the result is $2^1$-1= 2-1 = 1 ; So taking m=1(which is +ve) ,the base condition is satisfied.
Assuming Inductive Hypothesis as : P(k)= $2^k$-1 and lets assume P(k) to be true Now, we need to prove for P(k+1) but I am unable to solve ; please help me out!!!
A pigeonhole principle would go like this:
Modulo $m$ there are only $m$ distinct residues. Therefore at least one pair of the $m+1$ quantities $2^0,2^1,2^3,...,2^m$ must be identical $\bmod m$. Let $k$ and $l$ be the exponents of such an identical pair with $k>l$ (wlog). Then $2^k-2^l\equiv0\bmod m$. Therefore ... can you continue?
Note that $m$ has to be odd for $2$ to have a multiplicative inverse $\bmod m$, so that requirement must be added to the hypothesis.