4

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.

2 Answers2

1

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 .. –  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 03:36
0

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

Maged Saeed
  • 1,140
  • 1
    That's what I was looking for, thank you! –  Dec 13 '18 at 20:40
  • Oh, you are welcome. :) – Maged Saeed Dec 13 '18 at 20:40
  • @someone Euclid isn't needed to eliminate $n$ from $,18n!+!25\equiv 0\equiv 3n!+!4\pmod{!d}\ $ See my link on the question. – Bill Dubuque Dec 13 '18 at 20:41
  • 1
    @BillDubuque Yeah, I see how to do it without euclid –  Dec 13 '18 at 20:54
  • 1
    @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 .. –  Dec 13 '18 at 21:04
  • @someone When equations require only Integer solutions, like ours here, it is called Diophantine equations. They are named after the greek mathematician Diophantus who is the first to study such topic. In our case, $ax+by=c$, it is easy to solve it. But for higher degrees and other forms, it might be very hard to do. In fact, these types of equations are considered one the purest, and may be hardest, topics of mathematics. – Maged Saeed Dec 13 '18 at 21:10
  • 1
    @MagedSaeed Oh, okay, I'll look into it .. Thanks for detailed answer .. –  Dec 13 '18 at 21:13
  • Oh you are more than welcome. :)) – Maged Saeed Dec 13 '18 at 21:13
  • 1
    @MagedSaeed I'm just getting into number theory .. –  Dec 13 '18 at 21:13
  • 1
    I am sure You will enjoy it. Just keep practicing and be in touch with each topic. – Maged Saeed Dec 13 '18 at 21:14
  • @MagedSaeed Hey, just needed to get back on this, $(a, b) = (a, ax + by) = (ax + by, a)$ is not true in general, right ? But is it true that $(a, b) | (a, ax + by)$ and is equal when $ax + by \le |b|$ ? Similary for $(ax + by, b)$ .. Thanks. –  Dec 14 '18 at 19:00
  • @someone no it is true in general. Why do you say otherwise? do you have a counterexample? Moreover, this might be a typo but it is written as follows: $(a,b)=(a,b+ax) = (a+by,b)$ – Maged Saeed Dec 14 '18 at 19:05
  • $(5, 10) \ne (2 \times 5 + 10, 10)$, right ? Maybe you misread my comment .. –  Dec 14 '18 at 19:08
  • let $a = 5, b = 10, x = 2, y = 3$. We have $(5,10) = (5+102, 10) = (5,10+53) = 5$. Got it? – Maged Saeed Dec 14 '18 at 19:13
  • 1
    Just read my comment again, please. –  Dec 14 '18 at 19:14
  • Oh, you are talking about another case. I see. – Maged Saeed Dec 14 '18 at 19:14
  • 1
    It is true that $(a,b)|(a,ax+by)$. For the other case, I need to check. – Maged Saeed Dec 14 '18 at 19:18
  • 1
    Okay, thats good enough, thanks. –  Dec 14 '18 at 19:21
  • 1
    The first case can be proved as follows: $(a,ax+by)=(a,ax+by-ax) = (a,by)$. Now, $(a,b)|b \implies (a,b)|by \implies (a,b)|(a,by)$. – Maged Saeed Dec 14 '18 at 19:25