Instantly share code, notes, and snippets.

# naoto-ogawa/FermatsLittleTheorem.hs Created May 6, 2017

Testing Fermat's little theorem on Haskell
 {- Testing Fermat's little theorem on Haskell https://en.wikipedia.org/wiki/Fermat%27s_little_theorem \begin{align*} a^p &\equiv a \pmod{p} \end{align*} -} import Test.QuickCheck import Debug.Trace -- a prime number (beware of overflow) prime :: Integer prime = 13 -- left hand side funcLHS :: Integer -> Integer funcLHS x = rem (x^prime) prime -- right hand side funcRHS :: Integer -> Integer funcRHS x = rem x prime checkFermatsLittleTheorem :: Integer -> Bool checkFermatsLittleTheorem a = (funcLHS x) == (funcRHS x) where x = trace ("in=" ++ (show a) ++ ", funcLHS=" ++ (show $funcLHS a) ++ ", funcRHS=" ++ (show$ funcRHS a)) a main :: IO () main = quickCheck checkFermatsLittleTheorem
Owner

### naoto-ogawa commented May 6, 2017

 *Main> main in=0, funcLHS=0, funcRHS=0 in=0, funcLHS=0, funcRHS=0 in=2, funcLHS=2, funcRHS=2 in=3, funcLHS=3, funcRHS=3 in=3, funcLHS=3, funcRHS=3 in=-5, funcLHS=-5, funcRHS=-5 in=0, funcLHS=0, funcRHS=0 in=-3, funcLHS=-3, funcRHS=-3 in=8, funcLHS=8, funcRHS=8 in=8, funcLHS=8, funcRHS=8 in=5, funcLHS=5, funcRHS=5 in=-7, funcLHS=-7, funcRHS=-7 in=-2, funcLHS=-2, funcRHS=-2 in=-12, funcLHS=-12, funcRHS=-12 in=4, funcLHS=4, funcRHS=4 in=9, funcLHS=9, funcRHS=9 in=-3, funcLHS=-3, funcRHS=-3 in=-13, funcLHS=0, funcRHS=0 in=0, funcLHS=0, funcRHS=0 in=16, funcLHS=3, funcRHS=3 in=-13, funcLHS=0, funcRHS=0 in=2, funcLHS=2, funcRHS=2 in=-2, funcLHS=-2, funcRHS=-2 in=-13, funcLHS=0, funcRHS=0 in=-14, funcLHS=-1, funcRHS=-1 in=23, funcLHS=10, funcRHS=10 in=24, funcLHS=11, funcRHS=11 in=1, funcLHS=1, funcRHS=1 in=-18, funcLHS=-5, funcRHS=-5 in=16, funcLHS=3, funcRHS=3 in=-21, funcLHS=-8, funcRHS=-8 in=17, funcLHS=4, funcRHS=4 in=32, funcLHS=6, funcRHS=6 in=12, funcLHS=12, funcRHS=12 in=-11, funcLHS=-11, funcRHS=-11 in=-16, funcLHS=-3, funcRHS=-3 in=-30, funcLHS=-4, funcRHS=-4 in=-12, funcLHS=-12, funcRHS=-12 in=7, funcLHS=7, funcRHS=7 in=-22, funcLHS=-9, funcRHS=-9 in=38, funcLHS=12, funcRHS=12 in=8, funcLHS=8, funcRHS=8 in=-13, funcLHS=0, funcRHS=0 in=-30, funcLHS=-4, funcRHS=-4 in=1, funcLHS=1, funcRHS=1 in=-24, funcLHS=-11, funcRHS=-11 in=-31, funcLHS=-5, funcRHS=-5 in=28, funcLHS=2, funcRHS=2 in=30, funcLHS=4, funcRHS=4 in=21, funcLHS=8, funcRHS=8 in=-20, funcLHS=-7, funcRHS=-7 in=21, funcLHS=8, funcRHS=8 in=-18, funcLHS=-5, funcRHS=-5 in=-7, funcLHS=-7, funcRHS=-7 in=40, funcLHS=1, funcRHS=1 in=-22, funcLHS=-9, funcRHS=-9 in=37, funcLHS=11, funcRHS=11 in=-4, funcLHS=-4, funcRHS=-4 in=57, funcLHS=5, funcRHS=5 in=-35, funcLHS=-9, funcRHS=-9 in=-39, funcLHS=0, funcRHS=0 in=27, funcLHS=1, funcRHS=1 in=43, funcLHS=4, funcRHS=4 in=24, funcLHS=11, funcRHS=11 in=-32, funcLHS=-6, funcRHS=-6 in=59, funcLHS=7, funcRHS=7 in=-51, funcLHS=-12, funcRHS=-12 in=-51, funcLHS=-12, funcRHS=-12 in=58, funcLHS=6, funcRHS=6 in=-25, funcLHS=-12, funcRHS=-12 in=-24, funcLHS=-11, funcRHS=-11 in=-18, funcLHS=-5, funcRHS=-5 in=-69, funcLHS=-4, funcRHS=-4 in=-47, funcLHS=-8, funcRHS=-8 in=33, funcLHS=7, funcRHS=7 in=8, funcLHS=8, funcRHS=8 in=-56, funcLHS=-4, funcRHS=-4 in=29, funcLHS=3, funcRHS=3 in=20, funcLHS=7, funcRHS=7 in=-30, funcLHS=-4, funcRHS=-4 in=30, funcLHS=4, funcRHS=4 in=68, funcLHS=3, funcRHS=3 in=-61, funcLHS=-9, funcRHS=-9 in=-39, funcLHS=0, funcRHS=0 in=-32, funcLHS=-6, funcRHS=-6 in=34, funcLHS=8, funcRHS=8 in=-13, funcLHS=0, funcRHS=0 in=54, funcLHS=2, funcRHS=2 in=-87, funcLHS=-9, funcRHS=-9 in=32, funcLHS=6, funcRHS=6 in=47, funcLHS=8, funcRHS=8 in=-62, funcLHS=-10, funcRHS=-10 in=23, funcLHS=10, funcRHS=10 in=49, funcLHS=10, funcRHS=10 in=-31, funcLHS=-5, funcRHS=-5 in=91, funcLHS=0, funcRHS=0 in=75, funcLHS=10, funcRHS=10 in=28, funcLHS=2, funcRHS=2 in=82, funcLHS=4, funcRHS=4 in=58, funcLHS=6, funcRHS=6 +++ OK, passed 100 tests. *Main>