1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Do you know the Chinese Remainder Theorem? But for this exercise there's the immediate solution $x=1$. $\endgroup$ – Mateus Sampaio Oct 13 '14 at 23:17
  • 1
    $\begingroup$ 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. $\endgroup$ – quasicompactscheme Oct 13 '14 at 23:19
  • $\begingroup$ @galois right. but I keep checking and double checking my work yet I can't seem to find where I made the mistake $\endgroup$ – Math Major Oct 13 '14 at 23:26
  • $\begingroup$ Also I should note that CRT only applies for question (c) and doesn't tell you anything about solutions in questions (a) and (b) $\endgroup$ – quasicompactscheme Oct 14 '14 at 0:10
1
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.