Any suggestions of proving (non-)divisibility? What is the usual method? induction? by contradiction......?

Question

How do I prove that (21n+4)/(14n+3) is irreducible for every natural number n?

Answer 1

You prove that GCD(21n+4, 14n+3)= 1
(gcd = greatest common divisor)
21n+4 = 1 x (14n+3) + (7n+1) ===>
GCD(21n+3,14n+3) = GCD (14n+3, 7n+1)
14n+3= 2 x (7n+1) + 1 ===>
GCD(14n+3, 7n+1) = GCD(7n+1, 1)
we all know that GCD(any number, 1) = 1
this means that GCD(21n+4, 14n+3) = 1
this proves that 21n+4/14n+3 is irreducible for every n :)
this method is called "the Euclidean algorithm"
i hope this is helping.

Answer 2

Another Direct Proof : Observe that

3(14n+3) - 2(21n+4) = 1 . Any common factor present

divides the left side and therefore divides 1 on the right and

so must equal 1. Therefore the fraction cannot reduce

and is irreducible.

Answer 3

Induction looks like a good idea. Sometimes working through an inductive proof leads way to a direct proof, but usually the inductive process is a clear way to get your head in the right direction.

It might be useful to factor 21 from the top, 14 from the bottom (leaving 3/2 times a ratio of some n+x/y for top and bottom), and noting that divisibility would then require that your (n+a/b)/(n+x/y) be a multiple of 2. You should be able to prove that this is not possible, probably directly.

Wow, that might work...

Answer 4

Using the Euclidean algorithm, we see that
gcd(21n+4,14n+3)
=gcd(7n+1,14n+3)
=gcd(7n+1,7n+2)
=gcd(7n+1,1)
=1
So 21n+4 and 14n+3 have no common factors bigger than 1, therefore (21n+4)/(14n+3) is not reducible.

Answer 5

Let us presume that for some integer n, (21n+4)/(14n+3) is reducible. This means that there is some integer k such that k|(21n+4) *and* k|(14n+3), or that there exist integers a and b such that a*k = (21n+4) and b*k = (14n+3).

(21n+4)/(14n+3) = ak/bk = a/b.

Cross-multiply to get (21n+4)b = (14n+3)a --> 21bn + 4b = 14an + 3a
Solve for n: 21bn - 14an = 3a - 4b --> 7n(3b - 2a) = 3a - 4b --> -7n(2a - 3b) = 3a - 4b

--> n = (3a - 4b)/(-7(2a - 3b)) -->( (2a - 3b) + (a - b))/(-7(2a - 3b))

--> n = -1/7 + (a-b)/(-7(2a-3b))

Even if we found integers at random such that (a-b)/(-7(2a-3b)) is also an integer, the formula for n subtracts 1/7 from that. This means that n is not an integer, contradicting our earlier presumption.