1. ## Mods Help

Hey guys, havin trouble with this question

Using Euclids Algorithm, to find integers x and y satisfying 1127 $x$ + 2568 $y$ = 1, find solutions of

1. 1127 $c$ = 127 (mod 3568)

Note: From using Euclids Algorithm, i got the equation 1 = 1431 $\times$ 1127 - 452 $\times$ 3568..

Any help much appreciated..

2. Originally Posted by jvignacio
Hey guys, havin trouble with this question

Using Euclids Algorithm, to find integers x and y satisfying 1127 $x$ + 2568 $y$ = 1, find solutions of

1. 1127 $c$ = 127 (mod 3568)

Note: From using Euclids Algorithm, i got the equation 1 = 1431 $\times$ 1127 - 452 $\times$ 3568..

Any help much appreciated..
This means that $1431 \times 1127 \cong 1 \text{ mod } 3568$. What can you multiply $1431 \times 1127$ by to get $127$? What does this mean $c$ is?

3. Originally Posted by Swlabr
This means that $1431 \times 1127 \cong 1 \text{ mod } 3568$. What can you multiply $1431 \times 1127$ by to get $127$? What does this mean $c$ is?
So its like

$1127 \times c \cong 127 \text{ mod } 3568$

which means 3568 + 127 = 3695, so theres a NUMBER (c) that 1127 multiplies by that equals 3695?

4. Originally Posted by jvignacio
So its like

$1127 \times c \cong 127 \text{ mod } 3568$

which means 3568 + 127 = 3695, so theres a NUMBER (c) that 1127 multiplies by that equals 3695?
I'm a tad confused about what you are saying, although I suspect you are a tad confused about what $a \equiv b \text{ mod }n$ means. If $n \mid (a-b)$ then we write that $a \equiv b \text{ mod }n$. It is division, not equality. This is, essentially, just notation. So here you have that $1127 \times c \equiv 127 \text{ mod } 3568$, which means that $3568 \mid (1127 \times c - 127)$ but this is very inconvenient to work with, so it is better to stick to the modulo notation.

Modulo arithmetic is nice. Everything you want to work works. What we want to use here is that if $a \equiv b \text{ mod }n$ then $ac \equiv bc \text{ mod }n$ (This holds as $a \equiv b \text{ mod }n \Rightarrow n \mid a-b \Rightarrow n \mid c(a-b) \Rightarrow ac \equiv bc \text{ mod }n$). For example, $2 \equiv 7 \text{ mod }5$ and so $6 \equiv 21 \text{ mod }5$ (multiplying by 3).