# Math Help - Pigeonhole problem

1. ## Pigeonhole problem

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

2. 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 $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 $44^m$ and [tex]44^n[/Math], [tex]n<m[/Math]. Then, for some $a,a',r$, $44^m = 7a + r$ and $44^n=7a' + r$, hence $44^m-44^n=7(a-a')$. Because $44^m-44^n=44^n(44^{m-n}-1)$, this gives $44^n(44^{m-n}-1)=7(a-a')$, so that $7$ divides $44^n(44^{m-n}-1)$. In addition, $7$ and $44$ are relatively prime, hence we deduce that $7$ divides $44^{m-n}-1$. And $m-n\geq 1$. We are done.

3. thank you very much

4. Originally Posted by dajaka
SOLVED, THANX
It's not good form to delete questions. Now other members can't view it at a later date and perhaps learn something.

@Laurent: A good reason to always quote the question when replying .......

5. ok sorry
here is the problem again...