Waste less time on Facebook — follow Brilliant.

Modulo Arithmetic

If \( N\equiv a \pmod x\) and \( N\equiv b \pmod y \) such that x and y are co-prime . Consider \( N\equiv z \pmod {xy}\) ,how can we relate a , b ,z.

Note by Deep Chanda
3 years, 8 months ago

No vote yet
4 votes


Sort by:

Top Newest

Solving problems like these hinge on a very important property of the \(\gcd\) of two numbers. If \(d = \gcd(x,y)\), then there exists \(a,b \in \mathbb{Z}\) such that \[ax+by = d\] This is termed as Bezout's identity/lemma. The wiki link provides more details on this identity. In our case, we have \(N = a+k_1 x = b + k_2 y\). Hence, we get that \[k_1 x - k_2 y = b-a\] From Bezout's lemma, we have that there exists \(k_1,k_2 \in \mathbb{Z}\) for \[k_1x - k_2 y = b-a\] since \(\gcd(x,y) = 1\). Pick one such \(k_1^{*},k_2^{*} \in \mathbb{Z}\) i.e. we have \[k_1^* x - k_2^* y = b-a\] All the other solutions are given by \(\color{red}{k_1 = k_1^{*} + ny}\) and \(\color{red}{k_2 = k_2^{*} + nx}\) (since \( \gcd(x,y) = 1\) ), where \(n \in \mathbb{Z}\). Hence, \[N = a + k_1^{*} x + nxy = b + k_2^{*}y + nxy\] Note that the above is true since \(a + k_1^{*} x = b + k_2^{*}y\). Hence, \[N \equiv (a+k_1^{*}x) \pmod{xy} \equiv b+k_2^{*}y \pmod{xy}\] Marvis Narasakibma · 3 years, 8 months ago

Log in to reply

@Marvis Narasakibma Much better. Yong See Foo · 3 years, 8 months ago

Log in to reply

It looks like the Chinese Remainder Theorem for 2 equations. I guess it is that there exists \(N \equiv z \pmod{xy}\) which is a unique solution under \(\mathbb{Z}/xy\mathbb{Z}\), for \(N \equiv a \pmod {x}\) and \(N \equiv b \pmod {y}\) simultaneously if not mistaken. Yong See Foo · 3 years, 8 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...