# Math Help - Congruence proof

1. ## Congruence proof

I have to use congruence theory to prove $7|5^{2n}+3(2^{5n-2})$. I know this is just a matter of showing that $5^{2n}+3(2^{5n-2}) \equiv 0 (mod 5)$, but it's arriving at that result that's giving me trouble. By the way, this problem shows up in the section of my book where congruences are introduced, and I can only use basic properties of congruences in my proof. So, if there is some nice theorem that proves this quickly, chances are I'm not allowed to use it.

2. Originally Posted by spoon737
I have to use congruence theory to prove $7|5^{2n}+3(2^{5n-2})$. I know this is just a matter of showing that $5^{2n}+3(2^{5n-2}) \equiv 0 (mod 5)$, but it's arriving at that result that's giving me trouble. By the way, this problem shows up in the section of my book where congruences are introduced, and I can only use basic properties of congruences in my proof. So, if there is some nice theorem that proves this quickly, chances are I'm not allowed to use it.
I presume you meant
$5^{2n}+3(2^{5n-2}) \equiv 0 (mod 7)$

Can you use induction?

Let n = k = 1, then
$5^{2 \cdot 1} + 3(2^{5 \cdot 1 - 2}) = 5^2 + 3(2^3) = 25 + 24 = 49$
which is, of course, divisible by 7.

(Or if you want to do it "a modulo" then
$5 \equiv -2 \text{ (mod 7)}$

Thus
$5^{2 \cdot 1} + 3(2^{5 \cdot 1 - 2}) \equiv (-2)^{2} + 3(2^{5})(2^{-2}) \text{ (mod 7)}$

Now, $2^{-2} \equiv 2 \text{ (mod 7)}$ and $2^5 \equiv 4 \text{ (mod 7)}$, so

$5^{2 \cdot 1} + 3(2^{5 \cdot 1 - 2}) \equiv (-2)^{2} + 3(4)(2) \text{ (mod 7)}$

$\equiv 4 + 3 \equiv 0 \text{ (mod 7)}$

Now you need to show that if for n = k
$5^{2k} + 3(2^{5k - 2}) \equiv 0 \text{ (mod 7)}$

That for n = k + 1
$5^{2(k + 1)} + 3(2^{5(k + 1) - 2}) \equiv 0 \text{ (mod 7)}$

You can do that by, say, finding $5^{2k}$ from the n = k part of the statement, and subbing that into the n = k + 1 part.

-Dan

3. Oops, I did mean mod 7. Thanks a ton.

4. Hello, spoon737!

I have to use congruence theory to prove: $7\,|\,\left(5^{2n}+3\cdot2^{5n-2}\right)$
We have: . $5^{2n} + 3\cdot2^{5n}\cdot2^{-2}\text{ mod(7)}$

Since $5 \equiv -2\text{ mod(7)}\:\text{ and }\;2^{-2} \equiv 2\text{ (mod 7)}$

. . we have: . $(-2)^{2n} + 3\cdot2^{5n}\cdot2\text{ (mod 7)}$

Since $(-2)^{2n} \:=\:\left[(-2)^2\right]^n \:=\:4^{n} \;=\;\left[2^2\right]^n \:=\:2^{2n}$

. . we have: . $2^{2n} + 6\cdot2^{5n}\text{ (mod 7)}$

Factor: . $2^{2n}\left[1 + 6\cdot2^{3n}\right]\text{ (mod 7)}$

Since $6 \equiv -1\text{ (mod 7)}\:\text{ and }\:2^{3n} \:=\:\left(2^3\right)^n \;=\;8^n\:\equiv\:1^n\text{ (mod 7)}$

. . we have: . $2^{2n}\left[1 + (-1)(1)\right] \:=\:2^{2n}\cdot0 \:\equiv\:0\text{ (mod 7)}$

5. Originally Posted by Soroban
Hello, spoon737!

We have: . $5^{2n} + 3\cdot2^{5n}\cdot2^{-2}\text{ mod(7)}$

Since $5 \equiv -2\text{ mod(7)}\:\text{ and }\;2^{-2} \equiv 2\text{ (mod 7)}$

. . we have: . $(-2)^{2n} + 3\cdot2^{5n}\cdot2\text{ (mod 7)}$

Since $(-2)^{2n} \:=\:\left[(-2)^2\right]^n \:=\:4^{n} \;=\;\left[2^2\right]^n \:=\:2^{2n}$

. . we have: . $2^{2n} + 6\cdot2^{5n}\text{ (mod 7)}$

Factor: . $2^{2n}\left[1 + 6\cdot2^{3n}\right]\text{ (mod 7)}$

Since $6 \equiv -1\text{ (mod 7)}\:\text{ and }\:2^{3n} \:=\:\left(2^3\right)^n \;=\;8^n\:\equiv\:1^n\text{ (mod 7)}$

. . we have: . $2^{2n}\left[1 + (-1)(1)\right] \:=\:2^{2n}\cdot0 \:\equiv\:0\text{ (mod 7)}$

Ah yes. The simple and direct way. (So of course I missed it. )

-Dan

6. Thanks for the compliment, Dan!

It was direct, but not so simple . . .

While seeking the solution, I kept reaching for bigger and bigger hammers.
. . Eventually, I forced it to the desired conclusion.

Then I present it with "It is obvious to the meanest intelligence that ..."
. . preserving the illusion of my vast intelligence.

(My wife says my intelligence is half-vast. .I think that's what she said.)