How to solve modular equations? So for example $a \equiv i$ mod $x$, $a \equiv j$ mod $y$ for some given $i,j,x,y$ with $gcd(x,y)=1$, and I must find $a$ mod $x*y$. Any tips on how to do this? Specifically I want to calculate $a \equiv 1$ mod $16$, $a \equiv 3$ mod $17$, for example.
Asked
Active
Viewed 1,048 times
1
-
1See http://en.wikipedia.org/wiki/Chinese_remainder_theorem#Case_of_two_equations_.28k_.3D_2.29 – posilon Apr 10 '15 at 20:57
-
CRT = Chinese Remainder Theorem – Bill Dubuque Apr 10 '15 at 20:57
4 Answers
3
Since $a \equiv i \mod x$, we have $a = mx + i$, for some $m$ and likewise for your other equation, $a = ny + j$, for some $n$. Since both are $a$ equal something, they have to be equal to each other. So you have to solve $mx - ny = j - i$, for $m$ and $n$.
Makuta
- 140
2
Use the chinese remainder theorem
Rubertos
- 12,491
-
what $b$ are you talking about? Also it doesn't work for my example. – steedsnisps Apr 10 '15 at 20:56
-
I'm sorry.. I didn't sleep so I made a mistake. It's a chinese remainder theorem – Rubertos Apr 10 '15 at 20:59
2
I recommend referring to this website – it is extremely comprehensive and gives many valuable examples: http://www.millersville.edu/~bikenaga/abstract-algebra-1/modular-arithmetic/modular-arithmetic.html
Shrey
- 762
1
In this case there is a simple solution. Note $3\equiv3\mod16, (3+17)=20\equiv4\mod16$. The difference is $1$ so to arrive at $1\mod16$ we go back two lots of $17$ from $3$, i.e. $31$, and subtract this from $16.17=272$ to give the answer as $241$.
JMP
- 21,771