4
$\begingroup$

Prove $\frac{21n + 4}{14n + 3}$ is irreducible for every natural number $n$.

I was thinking of taking a number-theory based approach.

Can you suggest the following method

Calculus/Number theory based methods? Please take a look at my attempt here.

Assume $\frac{21n + 4}{14n + 3}$ is reducible so we can apply modular arithmethic, considering the numerator and denominator seperately. Ideas here,

$21n + 4 \equiv 4 (\mod 7)$ $14n + 3 \equiv 3 (\mod 7)$

$35n + 7 \equiv 7 (\mod 7)$

Taking the LHS separately, $35n + 7 (\mod 7) \equiv DNE$ there is no residue since there is no remainder.

Therefore, by contradiction, it is true?

Thanks!

$\endgroup$
  • $\begingroup$ You have shown that the numerator and denominator differ $\pmod 7$, but they could conceivably both be multiples of $11$, say. $\LaTeX$ hints: Instead of $==$ we usually use \equiv to get $\equiv$ when saying things are congruent and \pmod 7 gives $\pmod 7$ so you get the mod in the correct font. $\endgroup$ – Ross Millikan Sep 23 '14 at 17:54
  • 2
    $\begingroup$ Note that this is IMO 1959/1. $\endgroup$ – punctured dusk Sep 23 '14 at 18:06
2
$\begingroup$

We want to show that $21n+4$ and $14n+3$ are relatively prime. Note that $$(3)(14n+3)-(2)(21n+4)=1.$$ So any common divisor of $21n+4$ and $14n+3$ divides $1$.

Remark: I am not able to construct an argument based on the post. The remainder when $(21n+4)+(14n+3)$ is divided by $7$ is $0$, I would not use DNE, since $0$ is a perfectly respectable remainder. But working modulo $7$ is not enough, we want to rule out all common divisors greater than $1$.

$\endgroup$
2
$\begingroup$

gcd(21n+4, 14n+3) = gcd(14n+3, 7n+1) = gcd(7n+2, 7n+1) = gcd(7n+1, 1) = 1

Using repeated usage of Euclidean algorithm.

$\endgroup$
1
$\begingroup$

A simple one-line proof: $$\gcd(21n+4,14n+3)=\gcd(7n+1,14n+3)=\gcd(7n+1,7n+2)=1.$$

$\endgroup$
  • $\begingroup$ This is an exact duplicate of taninamdar's answer (posted 1 hour prior). $\endgroup$ – Bill Dubuque Jan 2 '15 at 19:54

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.