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
r
s
is considered modulo a number m, one will obtain the number
n
=
r
×
s
−
1
(
mod
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.
One puts
v
=
(
m
,
0
)
and
w
=
(
n
,
1
)
. One then repeats the following steps until the first component of w becomes
≤
N
. Put
q
=
⌊
v
1
w
1
⌋
, put z = v − qw. The new v and w are then obtained by putting v = w and w = z.
Then with w such that
w
1
≤
N
, one makes the second component positive by putting w = −w if
w
2
<
0
. If
w
2
<
D
and
gcd
(
w
1
,
w
2
)
=
1
, then the fraction
r
s
exists and
r
=
w
1
and
s
=
w
2
, else no such fraction exists.
