Modular equations

[Bodigrim]

Provide high-level functions to solve linear and quadratic equations by modulo.

Implement solveLinear satisfying propLinear and solveQuadratic satisfying propQuadratic.

solveLinear :: Mod m -> Mod m -> [Mod m]
solveLinear = undefined 

propLinear :: Mod m -> Mod m -> Bool 
propLinear a b = 
  all 
    (\x -> (a * x + b == 0) == x `elem` solutions) 
    [minBound .. maxBound]
  where 
    solutions = solveLinear a b

solveQuadratic :: Mod m -> Mod m -> Mod m -> [Mod m]
solveQuadratic = undefined 

propQuadratic :: Mod m -> Mod m -> Mod m -> Bool 
propQuadratic a b c = 
  all 
    (\x -> (a * x ^ 2 + b * x + c == 0) == x `elem` solutions) 
    [minBound .. maxBound]
  where 
    solutions = solveQuadratic a b

Applications: solveLinear can be used instead of solveCongruence in #110, solveQuadratic may be used to solve norm (z :+ 1) == 0 in quadratic fields (Gaussian, Eisenstein, etc.) for purposes discussed in #111.

[Bodigrim]

I'll assign myself to this issue.

[rockbmb]

@Bodigrim I was browsing other open issues since I put my two open PRs on hold while I solve some problems with them (one of them solved by this issue), I'll keep an eye on this to use it in #118.

[b-mehta]

@Bodigrim For efficient implementation of solveQuadratic for prime powers, Hensel's lemma is likely a good approach (and of course for other composites, the Chinese remainder theorem will reduce the problem to this case).