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

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.

• $a$ divides $(42n+37)-6(7n+4)=13$, so $a\in \{\pm 1, \pm 13\}$. – Sil Jun 27 at 20:01

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

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

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

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?