Results 1 to 12 of 12

Thread: Congruences, Powers, and Euler's Theorem

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

    Congruences, Powers, and Euler's Theorem

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

    Help pls
    Last edited by ReiKon; Jan 20th 2010 at 03: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
    22
    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 $\displaystyle 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 $\displaystyle 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
    22
    Quote Originally Posted by ReiKon View Post
    I think thats the one.

    O with a line in the middle.
    $\displaystyle \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
    $\displaystyle \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.

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

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

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

    $\displaystyle a \equiv 7^{3003} \pmod{m}$
    $\displaystyle a \equiv 7^{3003} \pmod{3750}$
    $\displaystyle a \equiv 7^{1000\times3+3} \pmod{3750}$
    $\displaystyle a \equiv (7^{1000})^3\times7^3 \pmod{3750}$
    $\displaystyle a \equiv 1\times7^3 \pmod{3750}$
    $\displaystyle a \equiv 7^3 \pmod{3750}$
    $\displaystyle a \equiv 343 \pmod{3750}$
    $\displaystyle However,\ 343\ is\ divisible\ by\ 7.$
    $\displaystyle So... a = 343 + 3750 = 4093$
    $\displaystyle Which\ is\ not\ divisible\ by\ 7.$
    $\displaystyle Therefore$
    $\displaystyle 4093 \equiv 7^{3003} \pmod{3750}$
    Last edited by ReiKon; Jan 20th 2010 at 02: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
    22
    Quote Originally Posted by ReiKon View Post
    Ok, I think I found the actual answer.
    Please correct me if I am wrong.

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

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

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

    $\displaystyle a \equiv 7^{3003} \pmod{m}$
    $\displaystyle a \equiv 7^{3003} \pmod{3750}$
    $\displaystyle a \equiv 7^{1000\times3+3} \pmod{3750}$
    $\displaystyle a \equiv (7^{1000})^3\times7^3 \pmod{3750}$
    $\displaystyle a \equiv 1\times7^3 \pmod{3750}$
    $\displaystyle a \equiv 7^3 \pmod{3750}$
    $\displaystyle a \equiv 343 \pmod{3750}$
    $\displaystyle However,\ 343\ is\ divisible\ by\ 7.$
    $\displaystyle So... a = 343 + 3750 = 4093$
    $\displaystyle Which\ is\ not\ divisible\ by\ 7.$
    $\displaystyle Therefore$
    $\displaystyle 4093 \equiv 7^{3003} \pmod{3750}$
    What makes you so sure that $\displaystyle \phi(3750)=1000\implies m=3750$? $\displaystyle \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 $\displaystyle \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 $\displaystyle \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 : $\displaystyle 7^{1000}\equiv 1 \pmod m$

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

    So $\displaystyle a\equiv 343 \pmod m$


    And since $\displaystyle \phi(m)=1000$, it follows that $\displaystyle 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
    22
    Quote Originally Posted by Moo View Post
    True. We have $\displaystyle \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 $\displaystyle \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 : $\displaystyle 7^{1000}\equiv 1 \pmod m$

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

    So $\displaystyle a\equiv 343 \pmod m$


    And since $\displaystyle \phi(m)=1000$, it follows that $\displaystyle 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.
    $\displaystyle 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.

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


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

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

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

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum