Find all the numbers $n$ such that $\frac{12n-6}{10n-3}$ can't be reduced.

Question

Find all the numbers $n$ such that $\frac{12n-6}{10n-3}$ can't be reduced.

Attempt:

It can't be reduced when $\gcd(12n-6,10n-3)=1$

Here $(a,b)$ denotes $\gcd(a,b)$

$$(12n-6,10n-3)=(12n-6,2n-3)=(12n-6,12n-18)=(12n-6,12)$$

$\Longrightarrow$ It can't be redused when $12\nmid 12n-6$ i.e when $12n\not\equiv 6\pmod{12}$

Theorem: for $ax\equiv b \pmod n$ there is a solution iff $d\mid b$ where $d=\gcd(a,n)$.

In this case $\gcd(12,12)=12$ so $d=12$ and $12\nmid 6$ therefore no solutions exists $\Longrightarrow$ it can be redused for all $n$.

I just want to verify my solution.

Answer 1

We have $(12n-6,2n-3)=(2n-3, 12)$. This is $1$ if $3$ does not divide $n$, and $3$ otherwise.

Remark: The assertion that $(12n-6,2n-3)=(12n-6,12n-18)$ is not true. You forgot to subtract.

Answer 2

hint: $\dfrac{12n-6}{10n-3}= 2-\dfrac{8n}{10n-3}$. Thus if it is reducible, then there is a $k \in \mathbb{N}$ such that: $k \mid 8n, k \mid (10n-3)$. Thus: $k \mid (10n-3) - 8n = 2n-3\implies k \mid 4(2n-3) = 8n -12\implies k \mid 8n - (8n-12) = 12$.

Answer 3

You got your application of Euclid's algorithm wrong.

If $n>1$ $$(12n-6,10n-3) = (10n-3,2n-3)$$ If $n=2$ this is immediately $1$.

If $n>7$ $$ (10n-3,2n-3) = (2n-3,12)$ $$ $2n-3$ is coprime to $12$ unless $n$ is divisible by $3$. So for $n>7$, the fraction is reducible only if $n = 3k$.

The remaining cases are $n \in \{3,4,5,6,7\}$ This is a manageable number to do by hand, and we find the fraction is reducible when $n=3$ or $n=6$

So in general the fraction is reducible if and only iff $n$ is divisible by $3$.

Answer 4

Hint $\,\ $ Both $\ \color{#90f}2,\ \color{#0a0}{2n\!-\!1}\,$ are coprime to $\,10n\!-\!3\,$ by EA = Euclid's Algorithm, so

$(10n\!-\!3,\, \underbrace{3\cdot\color{#90f}2\,(\color{#0a0}{2n\!-\!1})}_{\Large 12\,n-6})\, =\, (\color{#c00}{10n\!-\!3},3)\, \overset{\rm EA}=\, (\color{#c00}n,3)\,\ $ by $\,\ \color{#c00}{10n\!-\!3\equiv n}\pmod 3$

Answer 5

Below, for variety, is a purely equational proof, presented in great detail. Below we use the notation $\,[\![a]\!] = \color{#c00}{j\,[\![b]\!]} + k\,[\![c]\!]\,$ to denotes that the current equation is numbered $\,a,\,$ and that it was derived as $\,\color{#c00}j\,$ times equation $\,\color{#c00}b\,$ plus $\,k\,$ times equation $\,c.\,$ Here the method is more work than ad-hoc methods, but it will often be simpler and more straightforward in more complicated problems.

Lemma $\ (12n\!-\!6,10n\!-\!3) = (n,3).\, $ Proof $ $ We work mod the gcd $\, d = (12n\!-\!6,\, 10n\!-\!3).\,$ Starting from the given congruences $\,12n\equiv 6\,$ and $\,10n\equiv 3\,$ we derive further congruences by elimination, aiming to decrease the coefficients as much as possible. This yields the following

$$\begin{eqnarray} 12n &&\equiv 6\quad &&[\![1]\!]\\ 10n &&\equiv 3 && [\![2]\!]\\ 2n&&\equiv 3 && [\![3]\!] = \ \ [\![1]\!]-[\![2]\!]\\ 8n&&\equiv 0 && [\![4]\!] = 2[\![2]\!]-[\![1]\!]\\ 12&&\equiv 0 && [\![5]\!] = 4[\![3]\!]-[\![4]\!]\\ 6 &&\equiv 0 && [\![6]\!] = \ \ [\![1]\!]-[\![5]\!]n\\ 2n&&\equiv 0 && [\![7]\!]= \ \ [\![4]\!]-[\![6]\!]n\\ 3 &&\equiv 0 && [\![8]\!] = \ \ [\![3]\!]-[\![7]\!]\\ n &&\equiv 0 && [\![9]\!] = n[\![8]\!]-[\![7]\!] \end{eqnarray}\qquad$$

Thus $\,d\mid n,3\,$ so $\,d\mid (n,3).\,$ Conversely $\,\bar d\!:=(n,3)\mid n,3\,$ so $\,\bar d\mid 12n\!-\!6,\, 10n\!-\!3,\,$ so $\,\bar d\mid d .$ Hence, since $\,\bar d\mid d\mid \bar d\,$ we deduce $\,d = \bar d = (n,3)$.

Remark $\ $ The point is that we have converted the problem from calculation with divisibility relations to simpler calculation with arithmetical operations (here modular arithmetic, i.e. in the ring $\,\Bbb Z/n = \Bbb Z\ $ mod $\,n).$ Generally, we have much better intuition on the latter due to experience with integer arithmetic. Further, we can exploit any innate algebraic structure in the latter algebraic formulation, e.g. linear algebra (or module theory), e.g. Gaussian elimination, Hermite-Smith normal forms, Grobner bases, etc (such algebraic structure would be difficult if not impossible to elicit via divisibility calculus).

Answer 6

Like Find all the numbers $a,b$ such that $\frac{2a-b}{2a+b}$ can't be reduced,

if integer $d>0$ divides $12n-6,10n-3$

$d$ must divide $-5(12n-6)+6(10n-3)=12$

As $3|(12n-6),3\mid(12n-6,10n-3)\iff10n\equiv3\pmod3\iff n\equiv0\pmod3$

As $2|(12n-6),2\mid(12n-6,10n-3)\iff10n\equiv3\pmod2\iff n\equiv1\pmod2$

So for $(12n-6,10n-3)=1\iff n\equiv1,2\pmod3$ and $n\equiv0\pmod2$

$\iff n\equiv2,4\pmod6$

Answer 7

Another (general) way is to use Cramer's rule (or elimination) to solve for $\,n\,$ and $\,3\,$ below

$$\qquad\ \ \begin{eqnarray} 12\,n - 2\cdot 3 &=& i\\[.5em] 10\, n - 1\cdot 3 &\ =\ & j\end{eqnarray} \ \ \Rightarrow\ \ \begin{array}{} \color{#c00}{8\cdot n}\ =\ {-}1\cdot\,\color{#c00}i\, +\, 2\ \color{#c00}j \\[.5em] \color{#c00}{8\cdot 3}\ =\, {-}10\:\color{#c00}i\, +\, 12 \ \color{#c00}j \end{array} $$

By the right system a common divisor $d$ of $\color{#c00}{i,j}$ divides $\,\color{#c00}{8n},\,\color{#c00}{8\cdot 3}$ so also $n,3$ by $d$ odd, by $j$ odd.

By the left system a common divisor of $n,3$ divides $i,j.\,$ Thus $i,j$ and $n,3$ have the same set of common divisors, hence the same greatest common divisor, i.e. $\ \bbox[5px,border:1px solid #c00]{\gcd(i,j) = \gcd(n,3)}$

---

Remark $\ $ In the same way we can prove more generally

Theorem $ $ If $\rm\,(x,y)\overset{A}\mapsto (X,Y)\,$ is linear then $\: \rm\gcd(x,y)\mid \gcd(X,Y)\mid \color{#90f}\Delta \gcd(x,y), \ \ \color{#90f}{\Delta := {\rm det}\, A}$

e.g. $ $ above $\,\color{#90f}{\Delta =\bf 8}\,$ so the theorem yields $\ \gcd(n,3)\mid \gcd(12n\!-\!6,10n\!-\!3)\mid\color{#90f}{\bf 8}\cdot\gcd(n,3).\ $

The middle gcd $d$ is odd so $\,d\mid \color{#90f}8n\,\Rightarrow\, d\mid n,\,$ so $\,\gcd(n,3)\mid d\mid \gcd(n,3)\,\Rightarrow\, d = \gcd(n,3)$.