1
$\begingroup$

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.

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

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

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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?

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