Question

We know that we can reduce the base of an exponent modulo m: a(a mod m)k (mod m). But the same is not true of the exponent itself! That is, we cannot write aa mod m (mod m). This is easily seen to be false in general. Consider, for instance, that 210 mod 3 1 but 210 mod 3 mod 3 21 mod 3-2. The correct law for the exponent is more subtle. We will prove it in steps (a) Let R = {n є Z : 1-n-rn-1 Л gcd(n, m) = 1). Define the set aR = {ax mod m : x є R). Prove that aR- R for every integer a >0 with ged(a, m)-1. (b) Consider the product of all the elements in R modulo m and the elements in aR modulo m. By comparing those two expressions, conclude that, for all a E R, we have a(m)1 (mod m), where (m) R (c) Use the last result to show that, for any b > 0 and a R, we have ab-ab modo(m) (mod m) (d) Finally, prove the following two facts about the function ф above. First, if p is prime, then ф(p)-p Second, for any primes a and b with a b, we have o(ab-o(a)o(b). (Or slightly more challenging: show this second claim for all positive integers a and b with ged(a, b) 1.) The second fact of part (d) implies that, if p and q are primes, then o(M-(p-1)(q-1). That along with part (c) prove of the final claim from lecture about RSA, completing the proof of correctness of the algorithm.

Answer 1

"Given exponent modulus m: a^k identicalto (a mod m)^k (mod m) let us consider that R = {n elementof Z 1 lessthanorequalto n m - 1, gcd (n, m) = 1} OR = { a times mod m