diophantine.cpp File Reference

Primary module interface unit for module diophantine. More...

#include <cassert>
#include <tuple>
import base;

Include dependency graph for diophantine.cpp:

Functions
template<Integer T>
constexpr T	ntlib::diophantine_linear_univariate (T a, T b) noexcept
	Compute integer solutions to linear univariate diophantine equations.
template<Integer T>
constexpr std::tuple< T, T, T >	ntlib::diophantine_linear_bivariate (T a, T b, T c) noexcept
	Computes integer solutions to linear bivariate diophantine equations.

Detailed Description

Primary module interface unit for module diophantine.

Function Documentation

diophantine_linear_bivariate()

template<Integer T>

std::tuple< T, T, T > ntlib::diophantine_linear_bivariate ( T a, T b, T c )

nodiscardconstexprexportnoexcept

Computes integer solutions to linear bivariate diophantine equations.

Computes an integer solution \((x,y)\) to the diophantine equation \(ax + by = c\). A solution exists if and only if \(c\) is a multiple of \(\mathrm{gcd}(a,b)\). In this case, there are infinitely many solutions.

Template Parameters

T	An integer-like type.

Parameters

a	The coefficient of \(x\).
b	The coefficient of \(y\).
c	The absolute offset. Must be a multiple of \(\mathrm{gcd}(a,b)\).

Returns

A triple with \(x\), \(y\) and \(\mathrm{gcd}(a,b)\) where the latter can be used to compute other solutions using via Bezout's Identity. In case \(a = b = 0\), the third element is \(0\).

diophantine_linear_univariate()

template<Integer T>

T ntlib::diophantine_linear_univariate ( T a, T b )

nodiscardconstexprexportnoexcept

Compute integer solutions to linear univariate diophantine equations.

Computes an integer solution in \(x\) to the diophantine equation \(ax = b\). A solution exists if and only if \(b\) is a multiple of \(a\). For \(a = b = 0\) each \(x \in \mathbb{Z}\) is a solution and \(x = 0\) is returned. In all other cases the solution is unique.

Template Parameters

T	An integer-like type.

Parameters

a	The coefficient of \(x\).
b	The absolute offset. Must be a multiple of \(a\).

Returns

The solution in \(x\).