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
4 years, 8 months ago

No vote yet
4 votes

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

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 - 4 years, 8 months ago

Log in to reply

Much better.

Yong See Foo - 4 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 - 4 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...