El petit teorema de Fermat afirma que si p és un nombre primer, aleshores per a qualsevol nombre enter a, el nombre apàg– a és un múltiple enter de p.
Aquí p és un nombre primer
apàg≡ a (mod p).
Cas especial: Si a no és divisible per p, el petit teorema de Fermat és equivalent a l'enunciat que ap-1-1 és un múltiple enter de p.
ap-1≡ 1 (mod p)
O
ap-1% p = 1
Aquí a no és divisible per p.
Preneu un exemple Com funciona el petit teorema de Fermat
Exemple 1:
P = an integer Prime number a = an integer which is not multiple of P Let a = 2 and P = 17 According to Fermat's little theorem 2 17 - 1 ≡ 1 mod(17) we got 65536 % 17 ≡ 1 that mean (65536-1) is an multiple of 17>
Exemple 2:
Find the remainder when you divide 3^100,000 by 53. Since, 53 is prime number we can apply fermat's little theorem here. Therefore: 3^53-1 ≡ 1 (mod 53) 3^52 ≡ 1 (mod 53) Trick: Raise both sides to a larger power so that it is close to 100,000. = Quotient = 1923 and remainder = 4.Multiplying both sides with 1923: (3^52)^1923 ≡ 1^1923 (mod 53) 3^99996 ≡ 1 (mod 53)Multiplying both sides with 3^4: 3^100,000 ≡ 3^4 (mod 53) 3^100,000 ≡ 81 (mod 53) 3^100,000 ≡ 28 (mod 53).Therefore, the remainder is 28 when you divide 3^100,000 by 53.>
Ús del petit teorema de Fermat
Si sabem que m és primer, també podem utilitzar el petit teorema de Fermat per trobar la inversa.
am-1 ≡ 1 (mod m)>
Si multipliquem els dos costats per a-1, obtenim
a-1 ≡ a m-2 (mod m)>
A continuació es mostra la implementació de l'anterior:
C++
// C++ program to find modular inverse of a> // under modulo m using Fermat's little theorem.> // This program works only if m is prime.> #include> using> namespace> std;> // To compute x raised to power y under modulo m> int> power(>int> x, unsigned>int> y, unsigned>int> m);> // Function to find modular inverse of a under modulo m> // Assumption: m is prime> void> modInverse(>int> a,>int> m)> {> >if> (__gcd(a, m) != 1)> >cout <<>'Inverse doesn't exist'>;> >else> {> >// If a and m are relatively prime, then> >// modulo inverse is a^(m-2) mode m> >cout <<>'Modular multiplicative inverse is '> ><< power(a, m - 2, m);> >}> }> // To compute x^y under modulo m> int> power(>int> x, unsigned>int> y, unsigned>int> m)> {> >if> (y == 0)> >return> 1;> >int> p = power(x, y / 2, m) % m;> >p = (p * p) % m;> >return> (y % 2 == 0) ? p : (x * p) % m;> }> // Driver Program> int> main()> {> >int> a = 3, m = 11;> >modInverse(a, m);> >return> 0;> }> |
>
>
Java
// Java program to find modular> // inverse of a under modulo m> // using Fermat's little theorem.> // This program works only if m is prime.> class> GFG {> >static> int> __gcd(>int> a,>int> b)> >{> >if> (b ==>0>) {> >return> a;> >}> >else> {> >return> __gcd(b, a % b);> >}> >}> >// To compute x^y under modulo m> >static> int> power(>int> x,>int> y,>int> m)> >{> >if> (y ==>0>)> >return> 1>;> >int> p = power(x, y />2>, m) % m;> >p = (p * p) % m;> >return> (y %>2> ==>0>) ? p : (x * p) % m;> >}> >// Function to find modular> >// inverse of a under modulo m> >// Assumption: m is prime> >static> void> modInverse(>int> a,>int> m)> >{> >if> (__gcd(a, m) !=>1>)> >System.out.print(>'Inverse doesn't exist'>);> >else> {> >// If a and m are relatively prime, then> >// modulo inverse is a^(m-2) mode m> >System.out.print(> >'Modular multiplicative inverse is '> >+ power(a, m ->2>, m));> >}> >}> >// Driver code> >public> static> void> main(String[] args)> >{> >int> a =>3>, m =>11>;> >modInverse(a, m);> >}> }> // This code is contributed by Anant Agarwal.> |
>
>
Python 3
# Python program to find> # modular inverse of a> # under modulo m using> # Fermat's little theorem.> # This program works> # only if m is prime.> def> __gcd(a, b):> >if>(b>=>=> 0>):> >return> a> >else>:> >return> __gcd(b, a>%> b)> # To compute x^y under modulo m> def> power(x, y, m):> >if> (y>=>=> 0>):> >return> 1> >p>=> power(x, y>/>/> 2>, m)>%> m> >p>=> (p>*> p)>%> m> >return> p>if>(y>%> 2> =>=> 0>)>else> (x>*> p)>%> m> # Function to find modular> # inverse of a under modulo m> # Assumption: m is prime> def> modInverse(a, m):> >if> (__gcd(a, m) !>=> 1>):> >print>(>'Inverse doesn't exist'>)> >else>:> ># If a and m are relatively prime, then> ># modulo inverse is a^(m-2) mode m> >print>(>'Modular multiplicative inverse is '>,> >power(a, m>-> 2>, m))> # Driver code> a>=> 3> m>=> 11> modInverse(a, m)> # This code is contributed> # by Anant Agarwal.> |
>
>
C#
// C# program to find modular> // inverse of a under modulo m> // using Fermat's little theorem.> // This program works only if m is prime.> using> System;> class> GFG {> >static> int> __gcd(>int> a,>int> b)> >{> >if> (b == 0) {> >return> a;> >}> >else> {> >return> __gcd(b, a % b);> >}> >}> >// To compute x^y under modulo m> >static> int> power(>int> x,>int> y,>int> m)> >{> >if> (y == 0)> >return> 1;> >int> p = power(x, y / 2, m) % m;> >p = (p * p) % m;> >return> (y % 2 == 0) ? p : (x * p) % m;> >}> >// Function to find modular> >// inverse of a under modulo m> >// Assumption: m is prime> >static> void> modInverse(>int> a,>int> m)> >{> >if> (__gcd(a, m) != 1)> >Console.WriteLine(> >'Modular multiplicative inverse is '> >+ power(a, m - 2, m));> >else> {> >// If a and m are relatively prime, then> >// modulo inverse is a^(m-2) mode m> >Console.WriteLine(> >'Modular multiplicative inverse is '> >+ power(a, m - 2, m));> >}> >}> >// Driver code> >public> static> void> Main()> >{> >int> a = 3, m = 11;> >modInverse(a, m);> >}> }> // This code is contributed by vt_m.> |
>
>
PHP
// PHP program to find modular inverse of a // under modulo m using Fermat's little theorem. // This program works only if m is prime. // To compute x raised to // power y under modulo m // Recursive function to // return gcd of a and b function __gcd($a, $b) // Function to find modular // inverse of a under modulo m // Assumption: m is prime function modInverse($a, $m) { if (__gcd($a, $m) != 1) echo 'Inverse doesn't exist'; else { // If a and m are relatively // prime, then modulo inverse // is a^(m-2) mode m echo 'Modular multiplicative inverse is ', power($a,$m - 2, $m); } } // To compute x^y under modulo m function power($x, $y, $m) { if ($y == 0) return 1; $p = power($x,$y / 2, $m) % $m; $p = ($p * $p) % $m; return ($y % 2 == 0) ? $p : ($x * $p) % $m; } // Driver Code $a = 3; $m = 11; modInverse($a, $m); // This code is contributed by anuj__67. ?>> |
>
>
Javascript
> // Javascript program to find modular inverse of a> // under modulo m using Fermat's little theorem.> // This program works only if m is prime.> function> __gcd(a, b)> {> >if>(b == 0)> >{> >return> a;> >}> >else> >{> >return> __gcd(b, a % b);> >}> }> // Function to find modular inverse of a under modulo m> // Assumption: m is prime> function> modInverse(a, m)> {> >if> (__gcd(a, m) != 1)> >document.write(>'Inverse doesn't exist'>);> >else> {> >// If a and m are relatively prime, then> >// modulo inverse is a^(m-2) mode m> >document.write(>'Modular multiplicative inverse is '> >+ power(a, m - 2, m));> >}> }> // To compute x^y under modulo m> function> power(x, y, m)> {> >if> (y == 0)> >return> 1;> >var> p = power(x, parseInt(y / 2), m) % m;> >p = (p * p) % m;> >return> (y % 2 == 0) ? p : (x * p) % m;> }> // Driver Program> var> a = 3, m = 11;> modInverse(a, m);> // This code is contributed by rutvik_56.> > |
>
>
Sortida:
Modular multiplicative inverse is 4>
Complexitat temporal: O (log m)
Espai auxiliar: O(log m) a causa de la pila interna de recursivitat.
Alguns articles basats en el petit teorema de Fermat
- Calculeu nCr % p | Set 3 (utilitzant el petit teorema de Fermat)
- Invers multiplicatiu modular
- Test de primalitat | Set 2 (Mètode Fermat)
- Mòdul 10^9+7 (1000000007)