FERMATOVA MALÁ VĚTA - TECHCODEVIEW.COM

Fermatova malá věta říká, že pokud p je prvočíslo, pak pro jakékoli celé číslo a je číslo a^p– a je celočíselný násobek p.

Zde p je prvočíslo
A^p≡ a (mod p).

Speciální případ: Pokud a není dělitelné p, Fermatova malá věta je ekvivalentní tvrzení, že a^p-1-1 je celočíselný násobek p.

A^p-1≡ 1 (mod p)
NEBO
A^p-1% p = 1
Zde a není dělitelné p.

Vezměte si příklad, jak funguje malá Fermatova věta

Příklad 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>

Příklad 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.>

Použití malé Fermatovy věty

Pokud víme, že m je prvočíslo, můžeme také použít Fermatovu malou větu k nalezení inverze.

 am-1 ≡ 1 (mod m)>

Pokud obě strany vynásobíme a^-1, dostaneme

 a-1 ≡ a m-2 (mod m)>

Níže je uvedena výše uvedená implementace:

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;> }>

Jáva

// 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.>

Python3

# 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.> >

Výstup :

Modular multiplicative inverse is 4>

Časová náročnost: O (log m)

Pomocný prostor: O(log m) kvůli vnitřnímu zásobníku rekurze.

Nějaký článek založený na Fermatově malé větě

Vypočítejte nCr % p | Sada 3 (pomocí Fermatovy malé věty)
Modulární multiplikativní inverzní
Test primality | Sada 2 (metoda Fermat)
Modul 10^9+7 (1000000007)