Haskell Chinese Remainder Theorem

Question

Ich verstehe, dass, damit diese Funktion funktioniert crtHasSolution muss zuerst wahr Ich habe Probleme zu beweisen, dass n eine Lösung sein könnte irgendwelche Ideen oder Tipps, wie man das in Haskell schreiben oder überprüfen?

Ich weiß, dass die Bedingungen für N sind, dass es größer oder gleich 0 und kleiner als m ist, was das Produkt aller mod Basen ist.

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 = 

code

Answer 1

Von wikipedia:

Es ist leicht, zu prüfen, ob ein Wert von x eine Lösung ist: es genügt, den Rest der Division mit Rest zu berechnen von x von jedem [m_i].

Wenn x `mod` m_i /= a_i für jede i, dann ist x keine Lösung.

Diese schmatzt von Hausaufgaben, so anstatt geben Ihnen einen Einzeiler, die diese berechnet, werde ich Ihnen einige Leitfragen für die Implementierung von crtIsSolution n as ms geben:

• Ist n eine Lösung, wenn ms und as sind leer?
• Wenn Sie berechnen, ob n `mod` m_0 == a_0 und ob n ist eine Lösung für ms_0 und as_0, können Sie berechnen, ob n eine Lösung für m_0:ms_0 und a_0:as_0 ist?