Articles of greatest common divisor

Prove a set of nonnegative integers with greatest common divisor 1 and closed under addition has all but finite many nonnegative integers.

The question is to prove A set of nonnegative integers with greatest common divisor 1 and closed under addition has all but finite many nonnegative integers. I know there is a number theoretic proof which has presented by my textbook, but I don’t have much background in number theory. I would appreciate it if someone […]

Greatest common divisor of real analytic functions

Consider two real-valued real analytic functions $f$ and $g$. I want to prove that there exists a greatest common divisor $d$, which is a real analytic function. By greatest common divisor, I mean the following: Common divisor: There exist real analytic functions $q_1, q_2$ such that $f = dq_1, g = dq_2$, and Greateast: If […]

In a P.I.D., if $a^m = b^m$ and $a^n = b^n$ for $m, n \in \mathbb{N}$ with $\gcd(m,n) = 1$, then $a=b$

Let $R$ be a principal ideal domain, and $a, b \in R$ with $a^m = b^m$ and $a^n = b^n$ for $m, n \in \mathbb{N}$, and $\gcd(m, n) = 1$. I now want to show that we then already have $a = b$. I think the statement is easily seen to be true if $a […]

Count arrays with each array elements pairwise coprime

Given two integers $N$ and $M$ , How to find out number of arrays A of size N, such that : Each of the element in array, $1 ≤ A[i] ≤ M$ For each pair i, j ($1 ≤ i < j ≤ N$) $GCD(A[i], A[j]) = 1$ $M$ can be at max $100$. But […]

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

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 […]

Cancellative Abelian Monoids

Is there an example of cancellative Abelian monoid $M$ in which we may find two elements $x$ and $y$ such that they have a least common multiple but not a greatest common divisor?

Prove that $(ab,cd)=(a,c)(b,d)\left(\frac{a}{(a,c)},\frac{d}{(b,d)}\right)\left(\frac{c}{(a,c)},\frac{b}{(b,d)}\right)$

I’m working through Oystein Ore’s Number Theory and its History. On p. 109, I’m stuck on #2. The question asks the reader to verify the following identity [Note: $(x,y)=\gcd(x,y)$]: $$(ab,cd)=(a,c)(b,d)\left(\frac{a}{(a,c)},\frac{d}{(b,d)}\right)\left(\frac{c}{(a,c)},\frac{b}{(b,d)}\right)$$ I’ve tried numerous numeric examples and not found an exception. I’ve tried a messy proof, substituting sample factors and exponents, but it’s not very cohesive, […]

Definition of gcd in Euclidean domain dependent on valuation?

Let $D$ be Euclidean. In $\mathbb Z[i]$ our lecturer defined $\gcd (a,b)$ as the common divisor with greatest norm. I have a slight problem with this, since we actually fix the norm $N(a+bi)=a^2+b^2$. Does this definition indeed depend on the norm or is it actually equivalent to the general definition via the universal property $$c\mid […]

how to calculate double sum of GCD(i,j)?

I stumbled upon a programming question which wanted me to calculate : $$G(n) = \sum _{i=1}^{n} \sum _{j=i+1}^{n} gcd(i, j).$$ now I wrote a code to solve this problem but it takes polynomial time to solve this .I asked this question here but I think I need more mathematical insight before solving this algorithmicly. So […]

Proving that $\gcd(ac,bc)=|c|\gcd(a,b)$

This question already has an answer here: How to prove that $z\gcd(a,b)=\gcd(za,zb)$ 2 answers