Proving fraction is irreducible

Question

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.

Answer 1

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

Answer 2

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