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.
 A: 
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$.
A: Before answering your question, I will just give the following two facts:
Let $\gcd(a,b) = g$

  
*
  
*$g$ is the smallest positive integer such that $ax+by = g$ for any integers $x,y$.
  
*$$\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$$
