Intereting Posts

How to solve the equation $3x-4\lfloor x\rfloor=0$ for $x\in\mathbb{R}$?
Conditions for integrability
Show that the set $\mathbb{Q}(\sqrt{p})=\{a+b\sqrt{p}; a,b,p\in\mathbb{Q},\sqrt{p}\notin \mathbb{Q}\}$ is a field
Can the product of two non invertible elements in a ring be invertible?
Simple question about the definition of Brownian motion
What will be the one's digit of the remainder in: $\left|5555^{2222} + 2222^{5555}\right|\div 7=?$
Soft Question: Why does the Axiom of Choice lead to the weirdest constructions?
Counting ways to partition a set into fixed number of subsets
A game on a graph
How do you calculate this limit $\mathop {\lim }\limits_{x \to 0} \frac{{\sin (\sin x)}}{x}$?
Intersection of finite number of compact sets is compact?
Proof of Pitt's theorem
Proof of: $AB=0 \Rightarrow Rank(A)+Rank(B) \leq n$
“faces” of a non-planar graph
The accuracy from left to right and that from right to left of the floating point arithmetic sums

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$

- How to prove that $z\gcd(a,b)=\gcd(za,zb)$
- The product of n consecutive integers is divisible by n! (without using the properties of binomial coefficients)
- Supposed $a,b \in \mathbb{Z}$. If $ab$ is odd, then $a^{2} + b^{2}$ is even.
- Prove that every positive integer $n$ is a unique product of a square and a squarefree number
- Prove that we always have $ 2n \mid \varphi(m^n+p^n) $
- Pythagorean triples $(a,b,c)$ and divisibility of $a$ or $b$ by $3$.

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.

- Finding integer cubes that are $2$ greater than a square, $x^3 = y^2 + 2$
- Can an odd perfect number be divisible by $101$?
- Using Euler's Totient Function, how do I find all values n such that $\phi(n)=12$?
- Maximum possible gcd of integer elements, whose sum is 540.
- Is $n! + 1$ often a prime?
- If $n,k\in\mathbb N$, solve $3^k-1=x^n$.
- Does an elementary solution exist to $x^2+1=y^3$?
- How can I prove that $n^7 - n$ is divisible by $42$ for any integer $n$?
- Find $n$ such that $n/2$ is a square, $n/3$ is a cube, and $n/5$ a fifth power
- How many integers less than $1000$ can be expressed in the form $\frac{(x + y + z)^2}{xyz}$?

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.

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

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

**Hint** $\,\ $ Both $\ \color{#c00}2,\ \color{#0a0}{2n\!-\!1}\,$ are coprime to $\,10n\!-\!3\,$ by EA = Euclid’s Algorithm, hence

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

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$

Below, for variety, is a *purely equational* proof, presented in great detail. Below the notation $\,(a) = \color{#c00}{j(b)} + k (c)\,$ 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.

We work modulo 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, with a goal to decrease the coefficients as much as possible. This yields the following equations

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

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

- What does “homomorphism” require that “morphism” doesn't?
- For $n \geq 2$, prove that $(1- \frac{1}{4})(1- \frac{1}{9})(1- \frac{1}{16})…(1- \frac{1}{n^2}) = \frac{n+1}{2n}$
- Remainders of Fibonacci numbers
- Treatise on non-elementary integrable functions
- Why $\arccos(\frac{1}{3})$ is an irrational number?
- Why does this series $\sum_{n=0}^{\infty} \frac{(n!)^{2}}{(2n)!}$ converge?
- What is the sum of the reciprocal of primes? (Yes, it diverges)
- How to Prove $(A \times B) \otimes C + (B \times C) \otimes A + (C \times A) \otimes B = \bf{I}$?
- Catalan numbers – number of ways to stack coins
- Learning how to flip equations
- Hensel lift of a monic polynomial over $F_{2}$ in $Z_{8}$
- Euclidean Algorithm help!
- Expected number of matches when two shuffled rows of $52$ playing cards are lined up
- Painting a cube with 3 colors (each used for 2 faces).
- Simplify $\sqrt {\sqrt{5}-\sqrt{4}}$.