Results 1 to 6 of 6

Math Help - Congruence proof

  1. #1
    Junior Member
    Joined
    Feb 2007
    Posts
    70

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,675
    Thanks
    302
    Awards
    1
    Quote Originally Posted by spoon737 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2007
    Posts
    70
    Oops, I did mean mod 7. Thanks a ton.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,553
    Thanks
    542
    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)}


    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,675
    Thanks
    302
    Awards
    1
    Quote Originally Posted by Soroban View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,553
    Thanks
    542
    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.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 22nd 2010, 02:50 PM
  2. Congruence proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 10th 2009, 10:03 AM
  3. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 5th 2009, 09:34 AM
  4. another congruence proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 02:41 PM
  5. Proof congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 19th 2007, 09:13 AM

Search Tags


/mathhelpforum @mathhelpforum