Editing Fermat's little theorem (section)

== Generalizations ==
[[Euler's theorem]] is a generalization of Fermat's little theorem: For any [[modular arithmetic|modulus]] {{mvar|n}} and any integer {{mvar|a}} coprime to {{mvar|n}}, one has

<math display="block">a^{\varphi (n)} \equiv 1 \pmod n,</math>

where {{math|''φ''(''n'')}} denotes [[Euler's totient function]] (which counts the integers from 1 to {{mvar|n}} that are coprime to {{mvar|n}}). Fermat's little theorem is indeed a special case, because if {{mvar|n}} is a prime number, then {{math|1=''φ''(''n'') = ''n'' − 1}}.

A corollary of Euler's theorem is: For every positive integer {{mvar|n}}, if the integer {{mvar|a}} is [[coprime integers|coprime]] with {{mvar|n}}, then
<math display="block">x \equiv y \pmod{\varphi(n)}\quad\text{implies}\quad a^x \equiv a^y \pmod n, </math>
for any integers {{mvar|x}} and {{mvar|y}}.
This follows from Euler's theorem, since, if <math>x \equiv y \pmod{\varphi(n)}</math>, then {{math|1=''x'' = ''y'' + ''kφ''(''n'')}} for some integer {{mvar|k}}, and one has
<math display="block">a^x = a^{y + \varphi(n)k} = a^y (a^{\varphi(n)})^k \equiv a^y 1^k \equiv a^y \pmod n.</math>

If {{mvar|n}} is prime, this is also a corollary of Fermat's little theorem. This is widely used in [[modular arithmetic]], because this allows reducing [[modular exponentiation]] with large exponents to exponents smaller than {{mvar|n}}.

Euler's theorem is used with {{mvar|n}} not prime in [[public-key cryptography]], specifically in the [[RSA cryptosystem]], typically in the following way:<ref>{{citation|first1=Wade|last1=Trappe|first2=Lawrence C.|last2=Washington|title=Introduction to Cryptography with Coding Theory|year=2002|publisher=Prentice-Hall|isbn=978-0-13-061814-6|page=78}}</ref> if
<math display="block">y=x^e\pmod n,</math>
retrieving {{mvar|x}} from the values of {{mvar|y}}, {{mvar|e}} and {{mvar|n}} is easy if one knows {{math|''φ''(''n'')}}.<ref>If {{mvar|y}} is not coprime with {{mvar|n}}, Euler's theorem does not work, but this case is sufficiently rare for not being considered. In fact, if it occurred by chance, this would provide an easy factorization of {{mvar|n}}, and thus break the considered instance of RSA.</ref> In fact, the [[extended Euclidean algorithm]] allows computing the [[modular inverse]] of {{mvar|e}} modulo {{math|''φ''(''n'')}}, that is, the integer {{mvar|f}} such that
<math display="block">ef\equiv 1\pmod{\varphi(n)}.</math>
It follows that
<math display="block">x\equiv x^{ef}\equiv (x^e)^f \equiv y^f \pmod n.</math>

On the other hand, if {{math|1=''n'' = ''pq''}} is the product of two distinct prime numbers, then {{math|1=''φ''(''n'') = (''p'' − 1)(''q'' − 1)}}. In this case, finding {{mvar|f}} from {{mvar|n}} and {{mvar|e}} is as difficult as computing {{math|''φ''(''n'')}} (this has not been proven, but no algorithm is known for computing {{mvar|f}} without knowing {{math|''φ''(''n'')}}). Knowing only {{mvar|n}}, the computation of {{math|''φ''(''n'')}} has essentially the same difficulty as the factorization of {{mvar|n}}, since {{math|1=''φ''(''n'') = (''p'' − 1)(''q'' − 1)}}, and conversely, the factors {{mvar|p}} and {{mvar|q}} are the (integer) solutions of the equation {{math|''x''{{sup|2}} − (''n'' − ''φ''(''n'') + 1) ''x'' + ''n'' {{=}} 0}}.

The basic idea of RSA cryptosystem is thus: If a message {{mvar|x}} is encrypted as {{math|1=''y'' = ''x<sup>e</sup>'' (mod ''n'')}}, using public values of {{mvar|n}} and {{mvar|e}}, then, with the current knowledge, it cannot be decrypted without finding the (secret) factors {{mvar|p}} and {{mvar|q}} of {{mvar|n}}.

Fermat's little theorem is also related to the [[Carmichael function]] and [[Carmichael's theorem]], as well as to [[Lagrange's theorem (group theory)|Lagrange's theorem in group theory]].