1. ## Mods Help

Hey guys, havin trouble with this question

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

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

Note: From using Euclids Algorithm, i got the equation 1 = 1431 $\displaystyle \times$ 1127 - 452 $\displaystyle \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$\displaystyle x$ + 2568$\displaystyle y$ = 1, find solutions of

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

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

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

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

$\displaystyle 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

$\displaystyle 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 $\displaystyle a \equiv b \text{ mod }n$ means. If $\displaystyle n \mid (a-b)$ then we write that $\displaystyle a \equiv b \text{ mod }n$. It is division, not equality. This is, essentially, just notation. So here you have that $\displaystyle 1127 \times c \equiv 127 \text{ mod } 3568$, which means that $\displaystyle 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 $\displaystyle a \equiv b \text{ mod }n$ then $\displaystyle ac \equiv bc \text{ mod }n$ (This holds as $\displaystyle 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, $\displaystyle 2 \equiv 7 \text{ mod }5$ and so $\displaystyle 6 \equiv 21 \text{ mod }5$ (multiplying by 3).