$7\mid5^{2n}+3\cdot2^{5n-2}$; $43\mid6^{n+2}+7^{2n+1}$

Question

Use congruences to demonstrate $$7\mid5^{2n}+3\cdot2^{5n-2}$$ $$43\mid6^{n+2}+7^{2n+1}$$ When you are trying to see if something is divisible by 7, 8 or any number, do you automatically use that number as the modulus?

Answer 1

You can solve it by induction too ! (assuming that you are familiar with induction )

For the first one , assume P(n) to be true.

P(n+1) : $25.5^{2n }+ 3.2^{(5n-2)}.2^5 $which is congruent to $4.5^{2n }+ 3.2^{(5n-2)}.4 $which is divisible by 7 due to our hypothesis ( just take 4 outside).

For the second one , note that $ 6^{(n+2)}= -7.6^n ( mod 43 )$

So it suffices to show that $43| 7(7^{2n}-6^n)$

Again note that 43 and 7 are co prime and hence if we show that $7^{2n}=6^n( mod 43) $then we are done .

Again assume P(n) : $ 43 | 7^{2n}-6^n $ to be true

P(n+1) : $ 43| 49.7^{2n }-6.6^n $ .Note that 49 = 6 ( mod 43) hence take 6 outside and the result immediately follows.

Answer 2

I will show you for $7\mid5^{2n}+3\cdot2^{5n-2}$,same is for $43$

$gcd(7,5)=1\Rightarrow \phi(7)=6\Rightarrow5^{6}\equiv1\pmod7$

$gcd(2,5)=1\Rightarrow \phi(7)=6\Rightarrow2^{6}\equiv1\pmod7$ $$5^{2n}\equiv(5^{2})^{n}\equiv25^{n}\equiv4^{n}\equiv2^{2n}\pmod{7}$$ $2^{2n}\pmod{7}$ is cyclic: $$(n=1):2^{2}\equiv4\pmod{7}\\(n=2):2^{4}\equiv16\equiv2\pmod{7}\\(n=3):2^{6}\equiv64\equiv1\pmod{7}\\(n=4):2^{8}\equiv256\equiv4\pmod{7}\\(n=5):2^{10}\equiv1024\equiv2\pmod{7}\\(n=6):2^{12}\equiv4096\equiv1\pmod{7}$$ you see the pattern.

so: $if(n=3k=3t+3)\Rightarrow 2n=6k$ $$2^{6k}\equiv 2^{6k}\pmod{7}\equiv (2^{6})^{k}\equiv 1^{k}\equiv 1\pmod{7}$$ $$$$ $if(n=3k+1)\Rightarrow 2n=6k+2$ $$2^{6k+2}\equiv 2^{6k}\cdot2^{2}\pmod{7} \equiv [2^{6k}\pmod{7}\cdot2^{2}\pmod{7}] \\\equiv[(2^{6})^{k}\pmod{7}\cdot4\pmod{7}]\equiv[1^{k}\pmod{7}\cdot4\pmod{7}]\equiv4\pmod{7}$$ $$$$ $if(n=3k+2)\Rightarrow 2n=6k+4$ $$2^{6k+4}\equiv 2^{6k}\cdot2^{4}\pmod{7} \equiv [2^{6k}\pmod{7}\cdot2^{4}\pmod{7}] \\\equiv[(2^{6})^{k}\pmod{7}\cdot16\pmod{7}]\equiv[1^{k}\pmod{7}\cdot2\pmod{7}]\equiv2\pmod{7}$$

$$$$ Now we deal with: $3\cdot2^{5n-2}$

$if(n=3k=3t+3)\Rightarrow 5n-2=5(3t+3)-2=15t+1$ $$3\cdot2^{15t+1}\equiv 3\cdot2^{12t}\cdot2^{3t}\cdot2^{1}\equiv [3\pmod{7}\cdot2^{12t}\pmod{7}\cdot2^{3t}\pmod{7}\cdot2\pmod{7}]\\\equiv [3\cdot(2^{6})^{2t}\pmod{7}\cdot(2^{3})^{t}\pmod{7}\cdot2]\equiv [3\cdot1\cdot(8)^{t}\pmod{7}\cdot2]\equiv[3\cdot1\cdot1\cdot2]\equiv6\pmod{7} $$

so: $1+6\equiv0\pmod{7}$ $$$$ $if(n=3k+1)$ $$3\cdot2^{5n-2}\equiv 3\cdot2^{2n}\cdot2^{3n-2}\equiv [3\pmod{7}\cdot4\pmod{7}\cdot2^{9k+1}\pmod{7}]\\\equiv [3\cdot4\cdot2^{3k}\pmod{7}\cdot2^{6k}\pmod{7}\cdot2^{1}\pmod{7}]\equiv\\ [3\cdot4\cdot(8)^{k}\pmod{7}\cdot(2^{6})^{k}\pmod{7}\cdot2]\equiv[3\cdot4\cdot1\cdot1\cdot2]\equiv3\pmod{7} $$

so: $4+3\equiv0\pmod{7}$ $$$$ $if(n=3k+2)\Rightarrow 5n-2=2n+2n+n-2=2n+2n+3k+2-2=2n+2n+3k$ $$3\cdot2^{5n-2}\equiv 3\cdot2^{2n}\cdot2^{2n}\cdot2^{3k}\equiv [3\pmod{7}\cdot2\pmod{7}\cdot2\pmod{7}\cdot(8)^{k}\pmod{7}]\\\equiv [3\cdot2\cdot2\cdot1]\equiv5\pmod{7} $$

so: $2+5\equiv0\pmod{7}$

Answer 3

\begin{align*} 5^{2n}+3\cdot2^{5n-2} &= (7-2)^{2n}+ 3 \cdot 2^{3(n-1)} \cdot 2^{2n+1} \\ &= ((-2)^{2n} + 3 \cdot 8^{n-1} \cdot 2^{2n+1}) \mod 7 \\ &= ((-2)^{2n} + 3 \cdot 2 \cdot 2^{2n})\mod 7 \\ &= 2^{2n}(1+6) \mod 7 \\ &= 0 \mod 7 \end{align*} \begin{align*} 6^{n+2}+7^{2n+1} &= (6^{n+2} + 7 \cdot 49^n) \mod 43 \\ &= (36 \cdot 6^n + 7 \cdot 6^n) \mod 43 \\ &= 6^n (36+7) \mod 43 \\ &= 0 \mod 43 \end{align*}