Prove that there exists a positive integer n so that 44^n — 1 is divisible

by 7.

Printable View

- Oct 18th 2008, 02:20 AMdajakaPigeonhole problem
Prove that there exists a positive integer n so that 44^n — 1 is divisible

by 7. - Oct 18th 2008, 06:33 AMLaurent
There's no real need for a pigenhole principle here (look for little Fermat's theorem), but let's do it your way.

Consider the eight numbers $\displaystyle 44^0,44^1, 44^2,\ldots,44^7$. There are only 7 possible remainders in the division of these numbers by 7 (namely 0, 1,..., 6), hence at least two of these numbers have the same remainder modulo 7: this results from a pigeonhole principle. Let's say it is $\displaystyle 44^m$ and [tex]44^n[/Math], [tex]n<m[/Math]. Then, for some $\displaystyle a,a',r$, $\displaystyle 44^m = 7a + r$ and $\displaystyle 44^n=7a' + r$, hence $\displaystyle 44^m-44^n=7(a-a')$. Because $\displaystyle 44^m-44^n=44^n(44^{m-n}-1)$, this gives $\displaystyle 44^n(44^{m-n}-1)=7(a-a')$, so that $\displaystyle 7$ divides $\displaystyle 44^n(44^{m-n}-1)$. In addition, $\displaystyle 7$ and $\displaystyle 44$ are relatively prime, hence we deduce that $\displaystyle 7$ divides $\displaystyle 44^{m-n}-1$. And $\displaystyle m-n\geq 1$. We are done. - Oct 18th 2008, 06:39 AMdajaka
thank you very much :)

- Oct 18th 2008, 02:04 PMmr fantastic
- Oct 18th 2008, 02:41 PMdajaka
ok sorry

here is the problem again...