Imprecise Chinese Remainder Theorem with Fractions

209 Views Asked by At

I am familiar with how to use CRT on integers, but I have a case where I am operating on fractional values. For instance, say I have the equations

$$ x \equiv 6.8 \ \mathbf{mod} \ 10.1$$ $$ x \equiv 4.7 \ \mathbf{mod} \ 6.93$$

Is it possible to compute the smallest tolerance guaranteeing an answer before beginning the procedure? I.e. what is the smallest possible value of EPS in the code below? If EPS is too large I may miss a more precise solution.

EPS = 0.5 % some tolerance
x = 6.8;
while abs(mod(x, 6.93) - 4.7) > EPS
    if x >= 10.1*6.93
        sprintf('No solution.');
    end
    x = x + 10.1;
end

Edit: For the code above, the answer is $x=67.4$, since mod(67.4, 10.1) = 6.8 and mod(67.4, 6.93) = 5.03 which is within 0.5 of 4.7

I could iterate through $6.8, ..., n+10.1$ and return to the user the closest answer, but I was wondering if there was a way of predetermining that tolerance.

1

There are 1 best solutions below

3
On

I would scale everything up to integers so the system would be

$100x \equiv 680 \ \mathbf{mod} \ 1010\\ 100x \equiv 470 \ \mathbf{mod} \ 693 $

There might not be any solution because of gcd restrictions.