# Pigeonhole problem

• Oct 18th 2008, 02:20 AM
dajaka
Pigeonhole problem
Prove that there exists a positive integer n so that 44^n — 1 is divisible
by 7.
• Oct 18th 2008, 06:33 AM
Laurent
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 AM
dajaka
thank you very much :)
• Oct 18th 2008, 02:04 PM
mr fantastic
Quote:

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 .......
• Oct 18th 2008, 02:41 PM
dajaka
ok sorry
here is the problem again...