An integer when divided by $5$ and $13$ leaves residues $4$ and $7$ respectively

Question

Find an integer when divided by $5$ and $13$ leaves residues $4$ and $7$ respectively. (Without Modular Arithmetic).

I don't know if it is right, but I got this $$n=5x+4=13y+7$$

$$n=5(x-11)+59=13(y-4)+59$$ The $\operatorname{lcd}(5,13)=65$

So our number is every number like $n=65k+59$

I'll be glad if you enlighten me it.

Answer 1

${\bf Brute\ force}:\ \ 5\,\Bbb Z+\color{green}4 = \{\ldots, \color{#c00}{-6},-1,\color{green}4,9,13,\ldots\}$

$\qquad\qquad\qquad\ \ 13\Bbb Z+\color{orange}7 = \{\ldots, \color{#c00}{-6},\color{orange}7,20,\ldots\}\,\ $ so $\,\ n\equiv \color{#c00}{-6}\pmod{65 = \rm{lcm}(5,13)}\ $

$\bf Algorithmically,$ using CRT

$\quad\,\ {\rm mod}\ 5\!:\,\ n \equiv 4\equiv 7\!+\!13y \equiv 2\!-\!2y\iff 2\equiv -2y\iff \color{#0a0}{y\equiv -1}$

$\quad$ so its true iff $\ n = 7\!+\!13y = 7 \!+\! 13(\color{#0a0}{-1\!+\!5k}) = -6+65k,\ k\in\Bbb Z$

Answer 2

$5x - 13y = 7-4 = 3 \Rightarrow 5x = 15y + 3 - 2y \Rightarrow x = 3y + \dfrac{3-2y}{5} \Rightarrow 5\mid 3-2y \Rightarrow 3-2y = 5k \Rightarrow y = \dfrac{3-5k}{2} = \dfrac{3-k}{2} - 2k \Rightarrow 2\mid 3-k \Rightarrow 3-k = 2h \Rightarrow k = 3-2h \Rightarrow 3 - 5k = 3 - 5(3-2h) = -12 + 10h \Rightarrow y = \dfrac{3-5k}{2} = \dfrac{-12+10h}{2} = 5h-6 \Rightarrow n = 13y+7 = 13(5h-6)+7 = 65h-71 = 65(h-1) - 6 = 65t-6 = 65(t-1) + 59=65m+59, m \in \mathbb{Z}$

Answer 3

Hint: Use inspection :   $5x = 13 y + 3 \\ 13(1) + 3 = 16 \\ 13(2) + 3 = 29 \\ 13(3) + 3 = 42 \\ 13(4) + 3 = 5(11) \quad\checkmark \\ \therefore \forall k\in\mathbb Z: 5 (11+13k) = 13(4+5k) +3 \\[2ex] {\forall k\in\Bbb Z, \exists n\in\Bbb Z: \underline{\quad n = 59 + 65 k\quad}} $

Answer 4

Note that $13\times 2=26\equiv 1 \mod 5$

and $5\times 8=40\equiv 1 \mod 13$

So that $26x+40y \equiv x \mod 5; \equiv y \mod 13$ so we can put $x=4, y=7$ to obtain $104+280=384$ as one solution. We can obtain other solutions by adjusting by a multiple of $65$ - $390$ is obvious giving $-6$ and then $59$ by adding $65$.

The merit of this method, which relates closely to the Chinese Remainder Theorem (and Lagrange Interpolation for polynomials) is that it provides an automatic solution whatever values of $x$ and $y$ are given.

Answer 5

The question asks for any such integer, so note that $2\cdot13-5\cdot5=1$, now $13$ divides $1+5\cdot5$ and $5$ divides $1-2\cdot3$, so $$4(1+5\cdot5)+7(1-2\cdot13)=4\cdot26-7\cdot25=-71$$ is an example of such integer.