Open study

is now brainly

With Brainly you can:

  • Get homework help from millions of students and moderators
  • Learn how to solve problems with step-by-step explanations
  • Share your knowledge and earn points by helping other students
  • Learn anywhere, anytime with the Brainly app!

A community for students.

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

Mathematics
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Join Brainly to access

this expert answer

SIGN UP FOR FREE
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?
if im remembering the phi function correctly then if\[1681=\phi(2231)+k\] then we could reduce it to \[621^{k}\]
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 :)

Not the answer you are looking for?

Search for more explanations.

Ask your own question

Other answers:

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?
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 :)
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\).
Give me a hoot if you want an explanation of how to solve those two steps by hand.
Will revisit this question again next week, if you don't mind...
That's fine.
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.
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.

Not the answer you are looking for?

Search for more explanations.

Ask your own question