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

Get our expert's

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this

and **thousands** of other questions.

- anonymous

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

- schrodinger

See more answers at brainly.com

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this

and **thousands** of other questions

- anonymous

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?

- amistre64

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

- amistre64

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 :)

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- anonymous

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?

- amistre64

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 :)

- KingGeorge

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\).

- KingGeorge

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

- anonymous

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

- KingGeorge

That's fine.

- anonymous

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.

- KingGeorge

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.

Looking for something else?

Not the answer you are looking for? Search for more explanations.