Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

RolyPoly Group Title

How would you simplify it manually? \[621^{1681} mod 2231\]

  • one year ago
  • one year ago

  • This Question is Closed
  1. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Here's my attempt: (It's a bit long, so I separated it into three lines, but they should be in one line only) \[1681_{10} = 11010010001_{2}\] \[621^{1681} mod 2231 = 621^2mod2231)\times621mod2231)^2mod2231)^2\]\[\times 621mod2231)^2mod2231)^2mod2231)^2\]\[\times 621mod2231)^2mod2231)^2mod2231)^2mod2231)^2 \times 621mod2231\] Then, I got 1610 as the answer. Is there any faster way to do it manually?

    • one year ago
  2. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    if im remembering the phi function correctly then if\[1681=\phi(2231)+k\] then we could reduce it to \[621^{k}\]

    • one year ago
  3. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    2231 = 23*97, prime factors since prime numbers are relatively prime to one another; and since the phi value of any prime number is one less than the prime; phi(2231) = phi(23)*phi(97) = 22*96 = 2112 but my memory aint cooperating with me to see this clearly :)

    • one year ago
  4. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    This reminds me of n = pq , where p and q are prime numbers. ϕ(n) = (p-1)(q-1) choose 1< e ≤ ϕ(n), such that gcd (e, ϕ(n)) =1 ed mod ϕ(n) =1 d is the multiplicative inverse of e. But.. the above is not related to the question, I guess?

    • one year ago
  5. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    the RSA encryption uses the thrm yes; and i was just wondering if the thrm was applicable to simplify this. If we could simplify it to:\[\Large 621^{k\phi(2231)+m}\]then we might be able to play about with it ... just a thought :)

    • one year ago
  6. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Looking at this, and assuming we could factor these numbers, I might suggest the chinese remainder theorem.\[621^{1681}\pmod{2231}\implies621^{1681}\pmod{23*97}\]Since \(23|621\), we have that \[621^{1681}\equiv0\pmod{23},\]and we can calculate (it's fairly tedious, but possible by hand) that \[621^{1681}\equiv 58\pmod{97}.\]So we want some \(x\) such that \[x\equiv 23s\pmod{23}\]\[x\equiv58+97t\pmod{97}.\]Thus\[23s\equiv58\pmod{97}\]Another (tedious, but possible to do by hand) calculation shows that this means that \(s\equiv70\pmod{97}\). Then we plug it back into the original equation to get \(x=23(70)=1610\).

    • one year ago
  7. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Give me a hoot if you want an explanation of how to solve those two steps by hand.

    • one year ago
  8. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Will revisit this question again next week, if you don't mind...

    • one year ago
  9. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    That's fine.

    • one year ago
  10. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I can work out the line \(621^{1681}≡58 \pmod{97}\) using the method in my first post. Is there any alternative way to do it? For the rest of your first comment, since I haven't learnt the Chinese Remainder Theorem, I don't know why and how it works. I'm sorry that I need some more time to do a bit self-study before coming back to this question again.

    • one year ago
  11. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Well, since 97 is prime, and \(97\nmid 621\), we know that \(621^{96}\equiv1\pmod{97}\). So we find \(1681\equiv 49\pmod{96}\), and hence, \[621^{1681}\equiv39^{49}\pmod{97}.\]Then (I think this is fundamentally the same thing you did) you say \(49=2^5+2^4+2^0\). Thus, this is the same as\[39^{2^5}39^{2^4}39\pmod{97}.\]Then by repeatedly squaring, and reducing mod 97, you can find this number. Again, I think this is the same, in principle, of what you did.

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.