Jtdylktuy

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.

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

In general, for $a,b,c,d
inBbb N$, the following statements are equivalent:
$(i)$ there are integers $x,y$ s.t. $x(an+b)+y(cn+d)=1$ for all $nin 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 $nin Bbb N$.

Obviously $(ii)iff (iii)$ because $gcd(a,c)$ always divide $ad-bc$. In the case $ad-bcmid 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=0wedge bx+dy=1.$$
That is, $(x,y)$ is an integer solution to
$$begin{pmatrix}a&c\b&dend{pmatrix}begin{pmatrix}x\yend{pmatrix}=begin{pmatrix}0\1end{pmatrix}.$$
Observe that the determinant $ad-bc$ of $begin{pmatrix}a&c\b&dend{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&dend{pmatrix}$ is invertible and
$$begin{pmatrix}x\yend{pmatrix}=begin{pmatrix}a&c\b&dend{pmatrix}^{-1}begin{pmatrix}0\1end{pmatrix}=frac{1}{ad-bc}begin{pmatrix}d&-c\-b&aend{pmatrix}begin{pmatrix}0\1end{pmatrix}.$$
So $(x,y)=frac{1}{ad-bc}(-c,a)$. That is, $ad-bcmid c$ and $ad-bcmid a$. So $ad-bcmid 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 $nin 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=4nmidgcd(a,c)$). However, $(iv)$ is equivalent to the condition that for any prime divisor $p$ of $ad-bc$, there does not exist $ninBbb N$ such that $p$ divides both $an+b$ and $cn+d$.