Results 1 to 12 of 12

Math Help - Congruences, Powers, and Euler's Theorem

  1. #1
    Newbie ReiKon's Avatar
    Joined
    Jan 2010
    Posts
    6

    Congruences, Powers, and Euler's Theorem

    if \phi(m)=1000. Find a small no. that is not divisible by 7 that satisfies the congruence a \equiv 7^{3003} \pmod{m}

    Help pls
    Last edited by ReiKon; January 20th 2010 at 04:03 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by ReiKon View Post
    if F(m)=1000. Find a small no. that is not divisible by 7 that satisfies the congruence a = 7^3003 (mod m)

    Help pls
    What?? What is F(m)? I feel as though you are trying to use Euler's theorem.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie ReiKon's Avatar
    Joined
    Jan 2010
    Posts
    6
    Quote Originally Posted by Drexel28 View Post
    What?? What is F(m)? I feel as though you are trying to use Euler's theorem.
    I think thats the one.

    O with a line in the middle.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by ReiKon View Post
    I think thats the one.

    O with a line in the middle.
    \phi? Ok. So you are trying to use Euler's theorem. Do you know what it says and how to apply it?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie ReiKon's Avatar
    Joined
    Jan 2010
    Posts
    6
    Quote Originally Posted by Drexel28 View Post
    \phi? Ok. So you are trying to use Euler's theorem. Do you know what it says and how to apply it?
    A bit.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie ReiKon's Avatar
    Joined
    Jan 2010
    Posts
    6
    Ok, I think I found the actual answer.
    Please correct me if I am wrong.

    a \equiv 7^{3003} \pmod{m}; \gcd (a,m)
    \phi(m)=1000
    m=3750
    3750=5^4\times2\times3
    \phi(3750)=3750\left (1-\frac{1}{5}\right )\left (1-\frac{1}{2}\right )\left (1-\frac{1}{3}\right )
    \phi(3750)=3750\left (\frac{4}{5}\right )\left (\frac{1}{2}\right )\left (\frac{2}{3}\right )
    \phi(3750)=3750\left (\frac{4}{15}\right )
    \phi(3750)=1000

    gcd(7, 3750)
    3750 = 7 \times 535\ R\ 5
    7 = 5 \times 1\ R\ 2
    5 = 2 \times 2\ R\ 1
    2 = 1 \times 2\ R\ 0
    gcd(7, 3750) = 1

    7^{\phi(m)} \equiv 1 \pmod{m}
    7^{1000} \equiv 1 \pmod{3750}

    a \equiv 7^{3003} \pmod{m}
    a \equiv 7^{3003} \pmod{3750}
    a \equiv 7^{1000\times3+3} \pmod{3750}
    a \equiv (7^{1000})^3\times7^3 \pmod{3750}
    a \equiv 1\times7^3 \pmod{3750}
    a \equiv 7^3 \pmod{3750}
    a \equiv 343 \pmod{3750}
    However,\ 343\ is\ divisible\ by\ 7.
    So... a = 343 + 3750 = 4093
    Which\ is\ not\ divisible\ by\ 7.
    Therefore
    4093 \equiv 7^{3003} \pmod{3750}
    Last edited by ReiKon; January 20th 2010 at 03:52 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by ReiKon View Post
    Ok, I think I found the actual answer.
    Please correct me if I am wrong.

    a \equiv 7^{3003} \pmod{m}; \gcd (a,m)
    \phi(m)=1000
    m=3750
    3750=5^4\times2\times3
    \phi(3750)=3750\left (1-\frac{1}{5}\right )\left (1-\frac{1}{2}\right )\left (1-\frac{1}{3}\right )
    \phi(3750)=3750\left (\frac{4}{5}\right )\left (\frac{1}{2}\right )\left (\frac{2}{3}\right )
    \phi(3750)=3750\left (\frac{4}{15}\right )
    \phi(3750)=1000

    gcd(7, 3750)
    3750 = 7 \times 535\ R\ 5
    7 = 5 \times 1\ R\ 2
    5 = 2 \times 2\ R\ 1
    2 = 1 \times 2\ R\ 0
    gcd(7, 3750) = 1

    7^{\phi(m)} \equiv 1 \pmod{m}
    7^{1000} \equiv 1 \pmod{3750}

    a \equiv 7^{3003} \pmod{m}
    a \equiv 7^{3003} \pmod{3750}
    a \equiv 7^{1000\times3+3} \pmod{3750}
    a \equiv (7^{1000})^3\times7^3 \pmod{3750}
    a \equiv 1\times7^3 \pmod{3750}
    a \equiv 7^3 \pmod{3750}
    a \equiv 343 \pmod{3750}
    However,\ 343\ is\ divisible\ by\ 7.
    So... a = 343 + 3750 = 4093
    Which\ is\ not\ divisible\ by\ 7.
    Therefore
    4093 \equiv 7^{3003} \pmod{3750}
    What makes you so sure that \phi(3750)=1000\implies m=3750? \phi(6)=2=\phi(3)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    True. We have \phi(2^2 \times 5^4)=\phi(3\times 5^4)=\phi(2\times 3 \times 5^4)=1000

    But I think these are the only solutions.


    What's important in the fact that \phi(m)=1000 is that it's not possible that 7|m (you can do this very easily with a very short proof by contradiction). Thus gcd(7,m)=1 and we can apply Euler's theorem : 7^{1000}\equiv 1 \pmod m

    And 7^{3003}=(7^{1000})^3 \times 7^3 \equiv 7^3 \pmod m

    So a\equiv 343 \pmod m


    And since \phi(m)=1000, it follows that m>1000.

    So 343 is the number you're looking for.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Moo View Post
    True. We have \phi(2^2 \times 5^4)=\phi(3\times 5^4)=\phi(2\times 3 \times 5^4)=1000

    But I think these are the only solutions.


    What's important in the fact that \phi(m)=1000 is that it's not possible that 7|m (you can do this very easily with a very short proof by contradiction). Thus gcd(7,m)=1 and we can apply Euler's theorem : 7^{1000}\equiv 1 \pmod m

    And 7^{3003}=(7^{1000})^3 \times 7^3 \equiv 7^3 \pmod m

    So a\equiv 343 \pmod m


    And since \phi(m)=1000, it follows that m>1000.

    So 343 is the number you're looking for.
    Agreed!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie ReiKon's Avatar
    Joined
    Jan 2010
    Posts
    6
    But 343 is divisible by 7.
    343\div7=49
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Yes, but I never said it wasn't. I said that m mustn't be divisible by 7.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie ReiKon's Avatar
    Joined
    Jan 2010
    Posts
    6
    Ah. I think I found the answer I was looking for.
    Here it is.

    a \equiv 7^{3003} \pmod{m}; \gcd (a,m)
    \phi(m)=1000
    \phi(2^3\times5^3)=1000
    \phi(\left (1-\frac{1}{2}\right )\left (1-\frac{1}{5}\right )=1000
    \phi(\left (\frac{1}{2}\right )\left (\frac{4}{5}\right )=1000
    \phi(\left (\frac{2}{5}\right )=1000
    m=1000\times(\left (\frac{5}{2}\right )
    m=2500


    gcd(7, 2500)
    2500 = 7 \times 357\ R\ 1
    7 =  \times 7\ R\ 0
    gcd(7, 2500) = 1

    7^{\phi(m)} \equiv 1 \pmod{m}
    7^{1000} \equiv 1 \pmod{2500}

    a \equiv 7^{3003} \pmod{m}
    a \equiv 7^{3003} \pmod{2500}
    a \equiv 7^{1000\times3+3} \pmod{2500}
    a \equiv (7^{1000})^3\times7^3 \pmod{2500}
    a \equiv 1\times7^3 \pmod{2500}
    a \equiv 7^3 \pmod{2500}
    a \equiv 343 \pmod{2500}
    However,\ 343\ is\ divisible\ by\ 7.
    So... a = 343 + 2500 = 2843
    Which\ is\ not\ divisible\ by\ 7.
    Therefore
    2843 \equiv 7^{3003} \pmod{2500}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  2. Congruences, Powers, and Euler's Formula
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 23rd 2010, 07:26 PM
  3. powers and congruences
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 23rd 2009, 05:14 PM
  4. Congruences and Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 19th 2008, 08:26 AM
  5. De Moivre's Theorem finding powers
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: July 30th 2008, 10:27 AM

Search Tags


/mathhelpforum @mathhelpforum