# Prove that $44^n-1$ is divisible by $7$ for some $n$

How do I prove that there exists a positive integer n such that $44^n-1$ is divisible by $7$?

• By Fermat's little theorem, as long as $a$ is not divisible by a prime $p$, there is some $n$ so that $a^n-1$ is divisible by $p$. In particular, this will be true for $n=p-1$, regardless of the (suitable) choice of $a$. However, this is probably not how you're meant to do the problem. What method are you supposed to be using here? Aug 3, 2013 at 4:14
• Aug 3, 2013 at 4:17

Try with 44=42+2; then:

$(42+2)^n=42^n+ 42(....)+2^n= 2^n(mod7)$

Then you just need to find the least n with $2^n=1(mod7)$ , i.e., you just need to find an n so that $7|k(2^n -1)$ . Note that $2^1-1=1, 2^2-1=3,...$ and notice the remainders of $2^n-1$ when you divide by 7

• Replace $7|k(2^n -1)$ by $7|2^n -1$.
– Did
Aug 3, 2013 at 7:02

Let us test for $44^n-1\pmod 7$ for any $7$ consecutive positive integer values of $n$

If one the remainder is $0,$ we are done.

Else there will be definite repetition of remainder as we have at most $6$ in-congruent remainders for $7$ cases (pigeonhole principle)

Let $\displaystyle 44^{n_1}-1, 44^{n_2}-1$ same remainder where $n_1>n_2>0$

So, $7$ divides $\displaystyle 44^{n_1}-1-(44^{n_2}-1)=44^{n_2}(44^{n_1-n_2}-1)$

$\implies 7$ divides $\displaystyle 44^{n_1-n_2}-1$ as $(7,44)=1$

Since $\gcd(44,7) = 1$, by Fermat's little Theorem $$44^{7-1} \equiv 1\pmod 7.$$ So $44^6 - 1$ is divisible by $7$.