# Proving fraction is irreducible

Example:
The fraction $$\frac{4n+7}{3n+5}$$ is irreducible for all $$n \in \mathbb{N}$$, because $$3(4n+7) - 4(3n+5) = 1$$
and if $$d$$ is divisor of $$4n+7$$ and $$3n+5$$, it divides $$1$$, so $$d=1$$.

I want to know if there is some general method of finding $$x, y \in \mathbb{Z}$$, so that $$x(an+b) + y(cn+d) = 1$$ when $$(an+b, cn+d) = 1$$, instead of trial and error,
or some quicker and easier way (for not so pretty fractions) for determining whether it is irreducible.

• Heard of eulidian gcd algorithm ? – AgentS Dec 13 '18 at 19:53
• See this answer. – Bill Dubuque Dec 13 '18 at 19:57
• @someone first do you see why $\gcd(a, b)$ will be same as $\gcd(a-b, b)$ ? – AgentS Dec 13 '18 at 19:58
• Sorry, no knowledge in linear algebra, should've mentioned that .. – user626177 Dec 13 '18 at 19:59
• Find minimum of exponents in prime factorization ? – user626177 Dec 13 '18 at 20:12

Before answering your question, I will just give the following two facts:

Let $$\gcd(a,b) = g$$

1. $$g$$ is the smallest positive integer such that $$ax+by = g$$ for any integers $$x,y$$.
2. $$\gcd(a,b) = \gcd(a+bx, b) = \gcd(a,b+ax)$$

The proof of these two is elementary. In fact, it can be found somewhere here in this website.

Now, Euclidean Algorithm is used to find $$g$$ in $$(1)$$. How to apply this algorithm? you may refer to this website for more information.

In our case, the fraction is irreducible if and only if the greatest common divisor $$g$$ of the numerator and denominator is $$1$$. We can use the Euclidean Algorithm to find it, thought, and check.

Why do we need (2)?, Okay, this fact might be used as a shortcut to find $$g$$ in many occasions. For example, if I am given the following fraction and asked to prove it is irreducible: $$\frac{3n+4}{18n+25}$$ then I can use this shortcut as follows: $$\gcd(3n+4,18n+25) = \gcd(3n+4, (18n+25) -6(3n+4)) = \gcd(3n+4,1) = 1$$

• That's what I was looking for, thank you! – user626177 Dec 13 '18 at 20:40
• @BillDubuque Yeah, I see how to do it without euclid – user626177 Dec 13 '18 at 20:54
• @MagedSaeed Kinda off topic, but can this be used effectively for higher exponents than $1$ ? Polynomials is what I'm referring to. Just looking for yes or no answer, I'll work it out why .. – user626177 Dec 13 '18 at 21:04
• @MagedSaeed Oh, okay, I'll look into it .. Thanks for detailed answer .. – user626177 Dec 13 '18 at 21:13
• @MagedSaeed I'm just getting into number theory .. – user626177 Dec 13 '18 at 21:13

In general, for $$a,b,c,d \in\Bbb N$$, the following statements are equivalent:
$$(i)$$ there are integers $$x,y$$ s.t. $$x(an+b)+y(cn+d)=1$$ for all $$n\in \Bbb N$$;
$$(ii)$$ $$ad-bc$$ divides $$\gcd(a,c)$$;
$$(iii)$$ $$|ad-bc| =\gcd(a,c)$$.
Note also that any of the statements $$(i)$$, $$(ii)$$, and $$(iii)$$ implies that
$$(iv)$$ the rational number $$\frac{an+b}{cn+d}$$ is in the lowest form for all $$n\in \Bbb N$$.

Obviously $$(ii)\iff (iii)$$ because $$\gcd(a,c)$$ always divide $$ad-bc$$. In the case $$ad-bc\mid \gcd(a,c)$$, we can take $$x=-\frac{c}{ad-bc}$$ and $$y=\frac{a}{ad-bc}$$. So $$(ii)\implies (i)$$. We now prove that $$(i)\implies (ii)$$.

Suppose that such $$x$$ and $$y$$ exist. Then, $$ax+cy=0\wedge bx+dy=1.$$ That is, $$(x,y)$$ is an integer solution to $$\begin{pmatrix}a&c\\b&d\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}0\\1\end{pmatrix}.$$ Observe that the determinant $$ad-bc$$ of $$\begin{pmatrix}a&c\\b&d\end{pmatrix}$$ cannot be $$0$$ (otherwise $$(a,b)$$ and $$(c,d)$$ are proportional, and so $$an+b$$ and $$cn+d$$ are also proportional). That is, the matrix $$\begin{pmatrix}a&b\\c&d\end{pmatrix}$$ is invertible and $$\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}a&c\\b&d\end{pmatrix}^{-1}\begin{pmatrix}0\\1\end{pmatrix}=\frac{1}{ad-bc}\begin{pmatrix}d&-c\\-b&a\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix}.$$ So $$(x,y)=\frac{1}{ad-bc}(-c,a)$$. That is, $$ad-bc\mid c$$ and $$ad-bc\mid a$$. So $$ad-bc\mid \gcd(a,c)$$.

In your example, $$a=4$$, $$b=7$$, $$c=3$$, and $$d=5$$. So, $$ad-bc=-1 \mid \gcd(a,c)$$, and we can take $$x=-\frac{c}{ad-bc}=3$$ and $$y=\frac{a}{ad-bc}=-4$$.

I should like to mention that $$(iv)$$ is not equivalent to any of the statements $$(i)$$, $$(ii)$$, and $$(iii)$$. The rational numbers of the form $$\frac{2n+1}{2n+3}$$ is reduced for any $$n\in \Bbb N$$, but it does not meet $$(i)$$, $$(ii)$$, or $$(iii)$$ (i.e., $$(a,b,c,d)=(2,1,2,3)$$, so $$\gcd(a,c)=2$$, but $$ad-bc=4\nmid\gcd(a,c)$$). However, $$(iv)$$ is equivalent to the condition that for any prime divisor $$p$$ of $$ad-bc$$, there does not exist $$n\in\Bbb N$$ such that $$p$$ divides both $$an+b$$ and $$cn+d$$.

• Never studied linear algebra, but I guess I can use this as a shortcut without knowing why it's working .. – user626177 Dec 13 '18 at 20:52
• Why do you assume that the same $x$ and $y$ work for all $n,\,$ i.e. that they don't depend on $n$? – Bill Dubuque Dec 14 '18 at 3:36