Congruences in chinese remainder theorem

72 Views Asked by At

I'm trying to teach myself how to calculate xn, which is obtained thru linear congruence and given N

My example is: 99x==1(mod17) Which is 14x==1(mod17)

Now here is my problem. When I try finding the result to the equation, my lowest result is -6 (14x6 = 17x5)

However, when I input the problem into wolfram or other solvers, result is 11. How so, am I doing something wrong entirely?

2

There are 2 best solutions below

7
On BEST ANSWER

If we only allow positive integers as solutions $11$ is the smallest (which is congruent to $-6$ mod $17$)

0
On

You can do it multiple ways: $$14x=17y+1\equiv 3y+1\equiv 0\bmod 14\implies y\equiv {-1\over 3}\equiv -{15\over 3}\equiv -5\equiv 9\bmod 14 \\17(9)+1=14(9+2)=14(11)\implies x\equiv 11\bmod 17$$

is probably the easiest though.