6.042J Lecture Notes - Lecture 15: Riemann Hypothesis, Coprime Integers, Prime Number
13 Apr 2016
School
Course
Professor
Document Summary
The rsa crytosystem involves computing remained of number raised to large powers. A basic fact about remainders of powers follows from a theorem due to euler about congruences. For n > 0, (n) ::= the number of integers [0, n) that are relatively prime to n. If p is prime, the (p) = p-1 since every positive number in [0,p) is relatively prime to p. When n is a composite, the function gets a little complicated. Euler"s theorem: if n and k are relatively prime, then. This function is known as euler"s function. For example, (7) = 6 because all 6 positive number is [0,7) are relative prime to the number 7. The formula for the sum of an in nite series says. Substituting and so on for each prime number gives a sequence of equations:
