chinese_remainder Module Reference

Solve systems of modular congruences using the Chinese remainder theorem. More...

Classes
struct	ntlib::crt_congruence< T >
	Represents a single congruence x = a mod m. More...

Functions
template<Integer T>
constexpr crt_congruence< T >	ntlib::crt_coprime (const std::vector< crt_congruence< T > > &congruences) noexcept
	Solve a system of modular congruences for pairwise coprime moduli.
template<Integer T>
constexpr std::optional< crt_congruence< T > >	ntlib::crt (const std::vector< crt_congruence< T > > &congruences)
	Solve a general system of modular congruences.

Detailed Description

Solve systems of modular congruences using the Chinese remainder theorem.

Consider the following system of \(k\) modular congruences:

\[\begin{cases} a = a_1 \mod m_1 \\ a = a_2 \mod m_2 \\ \hphantom{a}~\vdots \\ a = a_k \mod m_k \end{cases} \]

Assuming that the \(m_i\) are pairwise coprime, the Chinese remainder theorem states that there is a unique solution \(x\) modulo \(M = \Pi_{i = 1}^k m_i\) solving all congruences simulatenously.

If the \(m_i\) are not pairwise coprime, there is either no solution or a unique solution modulo \(M = \mathrm{lcm}(m_1, \ldots, m_k)\).

Files
file	modules/chinese_remainder/chinese_remainder.cpp
	Primary module interface unit for module chinese_remainder.

---

Generated by  1.16.1