How do I prove that there exists a positive integer n such that $44^n-1$ is divisible by $7$?
$\begingroup$
$\endgroup$
2
asked Aug 3, 2013 at 4:08
-
$\begingroup$ 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? $\endgroup$– Ben GrossmannAug 3, 2013 at 4:14
-
$\begingroup$ artofproblemsolving.com/Wiki/index.php/… and en.wikipedia.org/wiki/… $\endgroup$– lab bhattacharjeeAug 3, 2013 at 4:17
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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
-
1
$\begingroup$
$\endgroup$
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$
answered Aug 3, 2013 at 5:08
$\begingroup$
$\endgroup$
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$.