Haskell中国剩余定理

Question

我理解，为了使这个函数工作，crtHasSolution必须是真的，首先，我很难证明n可以是一个解决方案--在haskell中如何编写或检查它的任何想法或技巧？

我知道，N的条件是，它必须大于或等于0，并且小于m，这是所有模基的乘积。

​

​

crtHasSolution :: [Integer] -> [Integer] -> Bool
crtHasSolution as ms = length as > 0 &&
                       length ms > 0 &&
                       length as == length ms &&
                       all (>=0) as &&
                       all (>=2) ms &&
                       pairwise_coprime ms

-- Is a given number a solution to a CRT problem?
-- usage: crtIsSolution n as ms = ans
-- assures: ans == True, if crtHasSolution as ms == True and n is a solution
--          ans == False, otherwise

crtIsSolution :: Integer -> [Integer] -> [Integer] -> Bool
crtIsSolution n as ms = crtHasSolution as ms &&
                        n >= 0 &&
                        n < m
                        where m =

代码

Answer 1

来自维基百科

很容易检查x的值是否是一个解决方案:按每个x计算x的欧几里德除法的剩余部分就足够了。

如果x `mod` m_i /= a_i用于任何i，那么x不是解决方案。

这有点家庭作业的味道，所以我将给您一些关于crtIsSolution n as ms实现的主要问题，而不是给您一个计算这个问题的一行。

• 如果n和as是空的，那么ms是一个解决方案吗？
• 如果您可以计算n `mod` m_0 == a_0和n是否是ms_0和as_0的解决方案，那么n是否是m_0:ms_0和a_0:as_0的解决方案？