Here's the question you clicked on:
RolyPoly
How would you simplify it manually? \[621^{1681} mod 2231\]
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 :)
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...
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.