# Rational reconstruction (mathematics)

In mathematics, rational reconstruction is a method that allows one to recover a rational number from its value modulo an integer. If a problem with a rational solution ${\displaystyle {\frac {r}{s}}}$ is considered modulo a number m, one will obtain the number ${\displaystyle n=r\times s^{-1}{\pmod {m}}}$. If |r| < N and 0 < s < D then r and s can be uniquely determined from n if m > 2ND using the Euclidean algorithm, as follows.[1]
One puts ${\displaystyle v=(m,0)}$ and ${\displaystyle w=(n,1)}$. One then repeats the following steps until the first component of w becomes ${\displaystyle \leq N}$. Put ${\displaystyle q=\left\lfloor {\frac {v_{1}}{w_{1}}}\right\rfloor }$, put z = v − qw. The new v and w are then obtained by putting v = w and w = z.
Then with w such that ${\displaystyle w_{1}\leq N}$, one makes the second component positive by putting w = −w if ${\displaystyle w_{2}<0}$. If ${\displaystyle w_{2} and ${\displaystyle \gcd(w_{1},w_{2})=1}$, then the fraction ${\displaystyle {\frac {r}{s}}}$ exists and ${\displaystyle r=w_{1}}$ and ${\displaystyle s=w_{2}}$, else no such fraction exists.