Modular Arithmetic/Number Theory

Question

(Not really sure about my work, so if you could tell me if I am on the right track that would be great!)

Find an integer x so that:

a. $x\equiv1\pmod{13}$ and $x\equiv1\pmod{36}$

Using the Euclidean algorithm:

$$36=13(2)+10$$ $$13=10(1)+3$$ $$10=3(3)+1$$ $$3=3(1)+0$$

$$1=17*36-47*13$$

$$x\equiv{1(17*36)+1(47*13)}\pmod{13*36}$$ $$x\equiv{612-611}\pmod{13*36}$$ $$x\equiv{1}\pmod{468}$$ $$x\equiv{1}$$

b. $x\equiv1\pmod{12}$ and $x\equiv8\pmod3$

$$x\equiv{253}$$

c. $x\equiv5\pmod{12}$ and $x\equiv19\pmod{35}$

$$x\equiv{89}$$

Answer 1

For (a) you forgot it should be $(-47\cdot 13)$, not $(47\cdot 13)$. Then you get the obvious answer, $x\equiv 1\pmod{13\cdot 36}$.

For (b), since $12$ and $3$ are not relatively prime, you need to first find out of the congruences are compatible.

For (c) Apply the same algorithm, solve $12x+35y=1$ and then take $$5\cdot 35\cdot y+19\cdot 12\cdot x\pmod{12\cdot 35}$$

Answer 2

1) You started it right, BUT you used the wrong formula for $x$ (you have a + instead of a -). It is much easier to observe that $x-1$ must be divisible by both $13$ and $36$. Therefore $x-1$ must be divisible by....

2) $12$ must divide $x-1$ and $3$ must divide $x-2$. But $3$ is a divisor of 12.

3) You need to solve it exactly as you solved 1), using the right formula for $x$.