haskell列表理解(数论问题)

Question

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

使用gcd(a,100)= 1找到每个a的最小数字b(a ^ b mod 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

这似乎是使用Carmichaelfunktionλ(x).它可以计算最小的指数米,使得一^米 ≡1模X为所有一,使得满足gcd(一个,X)= 1成立.因为λ(100)= 20,你要找的b是20.

您可以使用以下未经测试的Haskell表达式计算所有模块的解(上述公式中的x),该表达式或多或少直接翻译维基百科文章中解释的方法:

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

Answer 2

找出最小的数b

find f [1..]

对于每个 a (a^b mod 100) = 1

f b = all (\a -> a^b `mod` 100 == 1) xs

[每个a] gcd(a,100)=1

    where xs = [a <- [1..100], gcd a 100 == 1]