01110000 00111001 00110000 01111000 – day 3: done
On another note, i’ve been playing with Fermat’s Little Theorem. His Theorem is a way to determine if a number, N, is a prime without factoring.
Fermat’s Little Theorem:
if p is prime, then for every 1 ≤ a < p, then a^(p – 1) ≡ 1 (mod p)
I tested this by writing some code in Python:
#Fermat’s Little Theorem in Python
from math import exp
import random
number = input("Give me a number: ")
num = int(number)
a = random.randint(1,num-1)
b = a**(num-1)
if (b % num) == 1:
print("We have a prime!")
else:
print("Sorry, not a prime!")
#End of code
Of course, in math theory, there are some numbers that still pass this test, known as Carmichael Numbers. An example is 561 = 3 * 11 * 17 which fools the Fermat test. The solution is to merely run the test several times to ensure primality!