Congruence proof

**spoon737** · March 23rd 2008, 06:25 PM

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.

**topsquark** · March 23rd 2008, 06:39 PM

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

**spoon737** · March 23rd 2008, 06:45 PM

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

**Soroban** · March 23rd 2008, 09:24 PM

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)}$

**topsquark** · March 24th 2008, 03:59 AM

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

**Soroban** · March 24th 2008, 07:16 AM

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.)

Thread: Congruence proof

LinkBack

Thread Tools

Display

Congruence proof

Similar Math Help Forum Discussions

A Congruence Proof

Congruence proof

A Congruence Proof

another congruence proof

Proof congruence

Search Tags