list - haskell 列表理解(数论问题)

Question

我尝试在haskell中解决以下问题:

Find the smallest number b with (a^b mod 100) = 1 for every a with gcd(a,100)=1

我试过这个:

head[ b | a <- [1..], b <- [1..], (a^b `mod` 100) == 1, gcd a 100 == 1]

但这会产生 1^1 作为第一个解决方案，这是不正确的，它应该适用于每个 ;例如，3^1 不是解决方案。
我认为正确的解决方案是 b=20 但我希望它在 haskell 中。

Answer 1

这似乎是使用 Carmichael funktion λ(x)。它计算最小指数 m，使得 am ≡ 1 mod x 对所有 a 满足 gcd(a, x) = 1 成立。因为 λ(100) = 20，所以你要找的 b 是 20。

您可以使用以下未经测试的 Haskell 表达式计算所有模块的解决方案(上述公式中的 x)，该表达式或多或少是对 Wikipedia 文章中解释的方法的直接翻译:

import Data.Numbers.Primes

carmichael 1 = 1
carmichael 2 = 1
carmichael 4 = 2
carmichael n | isPowerOf 2 n    = n `div` 4
             | isPowerOf fac1 n = (n `div` fac1) * (fac1 - 1)
             | otherwise        = foldr1 lcm $ map (carmichael . product) grp
  where factors@(fac1:_) = primeFactors n
        grp              = group factors

isPowerOf n k | n == k         = True
              | k `mod` n == 0 = isPowerOf n (k `div` n)
              | otherwise      = False