# Modular Arithmetic/Number Theory

(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}$$

• Do you know the Chinese Remainder Theorem? But for this exercise there's the immediate solution $x=1$. – Mateus Sampaio Oct 13 '14 at 23:17
• CRT tells us nothing in this case other than that the answer exists, thats the point of the theorem. By the way, your answer to $1$ is wrong, its pretty easy to check correctness. – quasicompactscheme Oct 13 '14 at 23:19
• @galois right. but I keep checking and double checking my work yet I can't seem to find where I made the mistake – Math Major Oct 13 '14 at 23:26
• Also I should note that CRT only applies for question (c) and doesn't tell you anything about solutions in questions (a) and (b) – quasicompactscheme Oct 14 '14 at 0:10

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}$$

• For $c)$ it is probably easy to observe that $3*12=36$. – N. S. Oct 13 '14 at 23:32
• Sure I was just trying to leave something to the OP. :) @N.S. – Thomas Andrews Oct 14 '14 at 0:09

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$.