Prime Numbers. Show that if $a \mid 42n + 37$ and $a \mid 7n +4$, for some integer $n$, then $a = 1$ or $a = 13$

Question

Show that if $a \mid 42n + 37$ and $a \mid 7n +4$, for some integer $n$, then $a = 1$ or $a = 13$

I know most of the rules of divisibility and that any integer number can be expressed as the product of primes.

Given $a = \prod_{i=1}^\infty p_i^{\alpha_i}$ and $b = \prod_{i=1}^\infty p_i^{\beta_i}$

$a \mid b$ if and only of $\alpha_i \le \beta_i$ for every $i = 1, 2, 3, \ldots$

Even though i have this information, I cannot prove the statement. Help me please.

Answer 1

Hint $\bmod a\!:\,\ \color{#0a0}{ 37} \equiv -42n \equiv \overbrace{6(\color{#c00}{-7n}) \equiv (\color{#c00}{4})6}^{\Large \color{#c00}{-7n\ \ \equiv\ \ 4}} \equiv \color{#0a0}{24}\ \Rightarrow\ a\mid 13 = \color{#0a0}{37-24}$

Remark $\ $ If you are familiar with modular fractions then it can be written as

$\quad\ \ \ \ \bmod a\!:\ \ \dfrac{37}{42}\equiv -n \equiv \dfrac{4}{7}\equiv \dfrac{24}{42}\,\Rightarrow\, 37\equiv 24\,\Rightarrow\, 13\equiv 0$

Update $\ $ A downvote occurred. Here is a guess why. I didn't mention why those fractions exist. We prove $\,(7,a)=1$ so $\,7^{-1}\bmod n\,$ exists. If $\,d\mid 7,a\,$ then $\,d\mid a\mid 7n\!+\!4\,\Rightarrow\,d\mid 4\,$ so $\,d\mid (7,4)=1.\,$ Similarly $\,(42,a)=1\,$ by $\,(42,37)=1$.

Answer 2

Eliminate $n$

$a$ must divide $p(42n+37)-q(7n+4)=7n(6p-q)+37p-4q$ where $p,q$ are arbitrary integers

So, we need $6p-q=0$

The smallest positive integer value of $p$ is $1$

Answer 3

$$a|7n+4 \implies a|6(7n+4)=42n+24$$

$$ a|42n+37\text { and, } a|42n+24 \implies a|(42n+37)-(42n +24) = 13 $$

$$ a|13 \implies a=\pm 1, \text {or, } a=\pm 13 $$

Answer 4

If $a$ divides $42n+37$ and $a$ divides $7n+4,$

then $a$ divides $42n+37-6(7n+4)=13$.

Can you take it from here?