|
An important fact about prime number moduli is Fermat's little theorem: if p is a prime number and a is any integer, then ap is congruent to a modulo p. This was generalized by Euler: for any positive integer n and any integer a that is relatively prime to n, aφ(n) is congruent to 1 modulo n, where φ(n) denotes Euler's φ function counting the integers between 1 and n that are relatively prime to n. Euler's theorem is a consequence of the Theorem of Lagrange, applied to the group of units of the ring Zn. |
|
An important fact about prime number moduli is Fermat's little theorem: if p is a prime number and a is any integer, then :ap = a (mod p). This was generalized by Euler: for any positive integer n and any integer a that is relatively prime to n, :aφ(n) = 1 (mod n), where φ(n) denotes Euler's φ function counting the integers between 1 and n that are relatively prime to n. Euler's theorem is a consequence of the Theorem of Lagrange, applied to the group of units of the ring Zn. |
![[Home]](wikipedia.png)