0
$\begingroup$

Let $x$ be natural number such that

$\begin{cases} x=5k+3\\ x=3l+1 \end{cases}$ $k,l\in \Bbb N$

WolframAlpha says that $x=15n+13, n\in \Bbb N$. That's right because:

$15n+13=5(3n+2)+3=5k+3$

$15n+13=3(5n+4)+1=3l+1$

The question is: how WolframAlpha knows that $\begin{cases} x=5k+3\\ x=3l+1 \end{cases}$ $k,l\in \Bbb N \Longrightarrow x=15n+13 $ ?

$\endgroup$
1

2 Answers 2

2
$\begingroup$

As A.P. pointed out, you can use the Chinese Remainder Theorem for a system of two equations. Since we have: \begin{cases}x\equiv 3\mod{5}\\ x\equiv 1\mod{3}\end{cases} Applying the CRT, the general solution for $x$ will have the form: $$x\equiv\left(3\times 3\times\left[3^{-1}\right]_5+1\times 5\cdot\times\left[5^{-1}\right]_3\right)\mod{3\times 5}$$ where $[a^{-1}]_b$ is the multiplicative inverse of $a$ modulo $b$. Thus: $$x\equiv\left(9\times 2+5\times 2\right)\mod{15}$$ $$x\equiv 28\mod{15}$$ $$x\equiv 13\mod{15}$$ $$\therefore x=15n+13,\quad n\in\mathbb{N}$$

$\endgroup$
1
$\begingroup$

If $x=5k+3=3l+1$ then $5k+2=3l$. So $3$ divides $5k+2$, i.e. $3$ divides $3k+2k+2$, i.e. $3$ divides $2k+2$, i.e. $3$ divides $2(k+1)$, i.e. $3$ divides $k+1$, i.e. $k+1=3a$ for some $a$, i.e. $k=3a-1$. So $x=5k+3=5(3a-1)+3$ $=15a-2$ $=15(a-1)+13$, indeed $=15n+13$ for some $n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .