Commitfc95e7a

authored and

committed

Fermat's little theorem (#847)

* Fix typo* Add fermat's little theorem* Update fermat_little_theorem.py* Fix comments* Add Wikipedia reference

1 parentdd62f1b commitfc95e7aCopy full SHA for fc95e7a

File tree

+30

-0

lines changed

+30

-0

lines changed

Lines changed: 30 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,30 @@`
	`1`	`+# Python program to show the usage of Fermat's little theorem in a division`
	`2`	`+# According to Fermat's little theorem, (a / b) mod p always equals a * (b ^ (p - 2)) mod p`
	`3`	`+# Here we assume that p is a prime number, b divides a, and p doesn't divide b`
	`4`	`+# Wikipedia reference: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem`
	`5`	`+`
	`6`	`+`
	`7`	`+defbinary_exponentiation(a,n,mod):`
	`8`	`+`
	`9`	`+if (n==0):`
	`10`	`+return1`
	`11`	`+`
	`12`	`+elif (n%2==1):`
	`13`	`+return (binary_exponentiation(a,n-1,mod)*a)%mod`
	`14`	`+`
	`15`	`+else:`
	`16`	`+b=binary_exponentiation(a,n/2,mod)`
	`17`	`+return (b*b)%mod`
	`18`	`+`
	`19`	`+`
	`20`	`+# a prime number`
	`21`	`+p=701`
	`22`	`+`
	`23`	`+a=1000000000`
	`24`	`+b=10`
	`25`	`+`
	`26`	`+# using binary exponentiation function, O(log(p)):`
	`27`	`+print((a/b)%p== (a*binary_exponentiation(b,p-2,p))%p)`
	`28`	`+`
	`29`	`+# using Python operators:`
	`30`	`+print((a/b)%p== (ab* (p-2))%p)`

Comments

(0)