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

by 7.

Printable View

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

by 7. - Oct 18th 2008, 07: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 . 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 and [tex]44^n[/tex], [tex]n<m[/tex]. Then, for some , and , hence . Because , this gives , so that divides . In addition, and are relatively prime, hence we deduce that divides . And . We are done. - Oct 18th 2008, 07:39 AMdajaka
thank you very much :)

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

here is the problem again...