Questions tagged [gcd-and-lcm]

Use for questions related to gcd (greatest common divisor), lcm (least common multiple), and related concepts from integer and ring theory.

Filter by
Sorted by
Tagged with
0 votes
2 answers
23 views

What I am doing wrong when trying to solve: if $\gcd(a,b) = 1$, then $\gcd(2a+b,a+2b) \in \{1,3\}$?

First of all, I want to acknowledge that I had many of my questions closed because of duplicates. I am aware that this problem has been posted many times(here, here,here). I am not trying to get a ...
user avatar
0 votes
0 answers
38 views

Is there a general solution for gcd problems in for of if $\gcd(a,b) = 1$, then...? [duplicate]

I know that there are lots of questions with this format with duplicated answers: If $\gcd(a,b) = 1$, show that $\gcd(2a+b, a+2b)=1 \mbox{ or } 3$ Show that $\gcd(a + b, a^2 + b^2) = 1$ or $2$ if $\...
user avatar
0 votes
0 answers
33 views

Prove that if $\gcd(a,b) = 1$, than $\gcd(a+b,a^2+ b^2)$ is either $1$ or $2$ [duplicate]

Prove that if $\gcd(a,b) = 1$, than $\gcd(a+b,a^2+ b^2)$ is either $1$ or $2$ I found a solution for this using this idea, but I do not think my argument is right. Note $$d = \gcd(a+b,a^2+ b^2)\mid a+...
user avatar
0 votes
0 answers
15 views

Find all $x$ and $y$ $\in$ $Z$, such that $gcd(x,y) = 20$ and $lcm (x,y) = 420$ [duplicate]

This is what I tried to do, but I know it is wrong. $$\begin{cases} gcd(x,y) = 20 \\ lcm(x,y) = 420 \end{cases} $$ $$x = 20m$$ $$y = 20n$$ $$(m,n) \in \mathbb{Z}$$ $$420 = \frac{x\cdot y}{gcd(x,y)}$$ ...
user avatar
0 votes
3 answers
45 views

Find all positive integers $a$ such that: $lcm(120,a) = 360$ and $gcd(450,a)=90$

Find all positive integers $a$ such that: $lcm(120,a) = 360$ and $gcd(450,a)=90$ I started by factoring $$450 = 2\times 3\times3\times5\times5$$ and $$90 = 2 \times3\times3\times5$$ Since $gcd(450,a)=...
user avatar
0 votes
0 answers
27 views

Let $m$ and $n$ be positive integers such that $m = 24n + 51$. What is the largest possible value of the greatest common divisor of $2m$ and $3n$? [duplicate]

Let $m$ and $n$ be positive integers such that $m = 24n + 51$. What is the largest possible value of the greatest common divisor of $2m$ and $3n$? I'm trying to figure out how to use the Euclidean ...
user avatar
0 votes
0 answers
18 views

Multiple variable quadratic equation with congruence

I have the following equation: $A^2-3B^2+7C^2-21D^2=0$ and I have to prove that it does not have any non-trivial solution in $\mathbb{Z}^4$ . Using Congruence I deduced that $X,Z \equiv 0$ (mod $3$) ...
user avatar
  • 95
2 votes
1 answer
36 views

Series representation of GCD(x, y) [duplicate]

While playing around with WolframAlpha, I discovered that apparently the GCD of any integers x, y is equal to the following sum: $$ x + y - xy + 2\sum_{k = 1}^{x-1} \lfloor \frac{ky}{x}\rfloor $$ I've ...
user avatar
0 votes
2 answers
22 views

Equivalent integral quadratic forms properly represent the same integers

Definitions: An integral quadratic form (IQF) is some instance of $f(x,y)=ax^2+bxy+cy^2$, where $a,b,c \in \mathbb{Z}$. Let $f(x,y),g(x,y)$ denote IQFs. We say $f(x,y)$ and $g(x,y)$ are properly ...
user avatar
  • 165
-1 votes
0 answers
40 views

What is the fact Extended Euclidean Algorithm is based on? [duplicate]

I've started to wonder about something that should be easy enough to explain for one knowing the topic well enough, but I'm unable to derive that explanation. Euclidean Algorithm is based on a fact ...
user avatar
  • 177
1 vote
1 answer
24 views

Proving that $\alpha\gamma$ and $\beta\gamma$ have no gcd where $\alpha=3$ , $\beta=(1+2\sqrt{-5})$ and $\gamma=7(1+2\sqrt{-5})$in ring $Z[√(-5)]$

I have the following question before me : $\alpha=3$ and $\beta=1+2\sqrt{-5}$ are two elements of ring $R=Z[\sqrt{-5}]$. $\gamma=7(1+2\sqrt{-5})$ is another element of this ring. I have to prove that ...
user avatar
3 votes
0 answers
94 views

Divisors in GCD domain [duplicate]

Given a GCD domain $D$: $D$ is a GCD domain if for every two elements $a,b\in D$, $\exists d \in D\setminus \{0_D\} $ such that: (GCD.I) $d\mid a$ and $d\mid b$ (GCD.II) If $\exists c\in D\...
user avatar
0 votes
1 answer
52 views

Show: $\text{lcm}(a,a+p)=\text{lcm}(b,b+p), p \;\text{prime}\implies a=b$

(Romania Mathematical Olympiad). Let $a,b$ be positive integers such that exists a prime $p$ with the property $lcm(a,a+p)=lcm(b,b+p)$. Prove that $a=b$. What I could do: WLOG $p|a, p \nmid b \...
user avatar
2 votes
3 answers
106 views

If $ab+1 = r^2$ for $a,b,r \in \mathbb{N},$ how to show that $\gcd(2a(r+b)+1,2b(r+a)+1) = 1?$

Let $a<b$ be positive integers such that $ab+1 = r^2$ for some $r \in \mathbb{N}.$ If $m_1 = 2a(r+b)+1$ and $m_2 = 2b(r+a)+1.$ I want to find the possible values of $\gcd(m_1,m_2).$ I had taken ...
user avatar
0 votes
1 answer
51 views

How to show the coprimality? [closed]

Let $a,b,r\in \mathbb{N}$ such that $ab+1=r^2$ and $$m_1 = 2r(a+r)-1\\ m_2=2r(b+r)-1.\\$$ I want to know the possibile values of $\gcd(m_1,m_2),~\gcd(m_1,a)$ and $\gcd(m_2,b).$ Do all of those values ...
user avatar
1 vote
1 answer
50 views

To find the maximum possible value of their greatest common divisor $\gcd (a_1,a_2,\cdots, a_7)$.

The sum of seven distinct positive integers $a_1,a_2,\cdots, a_7$ is $315$. To find the maximum possible value of their greatest common divisor $\gcd (a_1,a_2,\cdots, a_7)$. If they were all equal ...
user avatar
  • 11.9k
3 votes
1 answer
54 views

gcd of $2$ numbers with multiplying on any prime number

We have two numbers $a$ and $b$ and $\gcd(a, b)$. We can multiply one of these numbers on any prime number. We need to get the most possible gcd. How can we do that? I had an idea like take all the ...
user avatar
1 vote
1 answer
103 views

We are allowed to erase the pair of numbers $(a, b)$ from the board and replace it with one of the following pairs: $(b, a), (a − b, b), (a + b, b)$.

A pair of integers are written on a blackboard. At each step, we are allowed to erase the pair of numbers $(a, b)$ from the board and replace it with one of the following pairs: $(b, a), (a − b, b), (...
user avatar
  • 11.9k
0 votes
0 answers
19 views

proof for -$\operatorname{lcm}(a,b,c,d) = \operatorname{lcm}(\operatorname{lcm}(a,b),\operatorname{lcm}(c,d))$ [duplicate]

lcm is associative in four natural numbers I would love for some help with : How to prove that $$\operatorname{lcm}(a,b,c,d) = \operatorname{lcm}(\operatorname{lcm}(a,b),\operatorname{lcm}(c,d))$$
user avatar
0 votes
0 answers
31 views

Does $\gcd(a, bc) = 1$ imply $\gcd(a, b) = 1$? [duplicate]

Assuming $a, b, c > 1$, then $(a, bc) = 1$ implies $b \not\mid a$, for if $b \mid a$, then we'd have $1 = (a, bc) \geq b > 1$ which is a contradiction. Likewise, $(a, bc) = 1$ also implies $c \...
user avatar
  • 1,059
1 vote
1 answer
49 views

I want $a := mk^2 + mkn$ and $b := mkn + \frac{n^2m}{2}$ to be coprime. That, is I want $\gcd(a, b) = 1$. Which constraints on $m, k, n$ lead to this?

Let $m$, $k$, and $n$ be integers with $m \geq 2$ being even. Let $a := mk^2 + mkn$ and $b := mkn + \frac{n^2m}{2}$. How can I simplify $\gcd(a, b)$? Namely, how can I simplify $$\gcd\left(mk^2 + mkn,\...
user avatar
  • 1,059
1 vote
0 answers
47 views

Find the least common multiple of three polynomials [duplicate]

I am recently writing a math module about polynomials in python. And I encountered this question when it comes to compute the least common multiple of several polynomials. Let [] denote lcm and let () ...
user avatar
  • 465
0 votes
0 answers
13 views

Solving maximization problem with linear combination

I am trying to find the maximum value of: $$nA - \lfloor \frac{nA}{B} \rfloor B $$ for any $n$, where $n$, $A$, and $B$ are all positive integers. I already know the answer: $B - gcd(A,B)$. What I'm ...
user avatar
8 votes
0 answers
163 views

Forming rational numbers using unique Egyptian fractions, all but one of whom have coprime denominators

Question: For a given rational number $r\in (0,1)$, does there exists a finite $S\subset \mathbb{N}$ such that every pair of elements of $S$ are coprime and $$r-\sum_{n\in S}\frac{1}{n}=\frac{1}{b}$$ ...
user avatar
  • 9,405
4 votes
2 answers
64 views

Approximate LCM (Least Common Multiple) of $n$ random $k$-digit numbers

I choose $n$ different $k$-digit numbers randomly. I was wondering, roughly, what one can expect their LCM (least common multiple) to be? Preferably in Big O (or Big $\Theta$) notation. I'm particular ...
user avatar
  • 1,612
-1 votes
1 answer
131 views

Show $\gcd(n, 2^{2^n}+1)=1$ [duplicate]

I am trying to show that $n$ and $2^{2^n}+1$ are coprime for all $n \in \mathbb{N}$. My intuition tells me induction is a good method. When $n=1$, $\gcd(1, 2^{2^1}+1)=\gcd(1, 5)=1$. Now suppose $\gcd(...
user avatar
1 vote
0 answers
22 views

An exact sequence of cyclic groups related to the lcm

The sequence $0 \longrightarrow\mathbb{Z}/(a\vee b \vee c)\mathbb{Z} \underset{\phi_1}{\longrightarrow} \mathbb{Z}/a\mathbb{Z} \bigoplus \mathbb{Z}/b\mathbb{Z} \bigoplus \mathbb{Z}/c\mathbb{Z}\...
user avatar
  • 3,270
2 votes
0 answers
26 views

Suppose $x,y,z$ are mutually coprime positive integers that solve $x^2+y^2=z^2$ [duplicate]

Suppose $x,y,z$ are mutually coprime positive integers that solve $x^2+y^2=z^2$.Assume that $x$ is odd and exactly one of $y$ or $z$ is even. Show that $z-y$ and $z+y$ are coprime. So I started of by ...
user avatar
  • 21
1 vote
1 answer
23 views

Uniqueness of GCD when considering all integers. [duplicate]

I have a book that says that 6 and -6 are both greatest common divisors of 12 and 18, and thus a gcd is not uniquely defined. I have an obvious question about this. 6 >-6 so how is -6 also a gcd? I ...
user avatar
  • 149
0 votes
1 answer
25 views

Euclidian Algorithm: proof that $n_i < \frac{n_{i-2}}{2}\quad \forall i\geq 2$ [closed]

In the euclidian algorithm to find the greatest common denominator $\text{gcd}(n,m)$ of $n$ and $m$ ($m\leq n$) I want to prove the following: $n_i < \frac{n_{i-2}}{2}\quad \forall i\geq 2$ where $...
user avatar
1 vote
0 answers
49 views

Space obtained by attaching two $2$-cells to $S^1$

I am working on the following problem: Let $X$ be the CW complex obtained from $S^1$ by attaching two $2$-cells: one by a map of degree $2$, and one by a map of degree $3$. (a) Compute the homology ...
user avatar
0 votes
1 answer
21 views

Greatest common divisor: Euclidian Algorithm, missing proof step [duplicate]

I'm working through the Euclidian Algorithm to find the greatest common divisor of two integers $n,m$. However I'm stuck at a very trivial step before the algorithm is even presented: $n,m\in \mathbb{...
user avatar
0 votes
0 answers
25 views

Fitting a noisy and incomplete arithmetic progression

I have a sequence of numbers that I know they belong to an arithmetic progression. I do not know the value of offset ($b$), the difference between consecutive numbers $\Delta$, nor the actual position ...
user avatar
  • 123
2 votes
1 answer
43 views

Demonstrating Equivalent GCDs [duplicate]

I am attempting to prove that: $gcd(n^2-100n, 2n+1) = gcd(n-100, 201)$ To do so, I'm making use of the Euclidean algorithm, but I'm not getting to any result that I find particularly useful in ...
user avatar
  • 946
5 votes
3 answers
365 views

Prove that $\frac{a-c}{k}=\frac{d+b}{n}$, where $N=a^2+b^2=c^2+d^2$ and $k=\gcd(a-c,d-b)$, $n=\gcd(a+c, d+b)$

Let $N$ be odd and $N = a^2 + b^2 = c^2 + d^2$, where $a, b, c, d \in \mathbb{N}$ and WLOG let $a, c$ be odd, $b, d$ be even, $a > c$, and $b < d$. Prove that $\frac{a-c}{k}=\frac{d+b}{n}$. I ...
user avatar
4 votes
1 answer
86 views

In a group, when does $|ab| = \mathrm{lcm}(|a|, |b|)$

In a finite abelian group $G$ where $a$ has order $m$ and $b$ has order $n$, I was able to prove that $\mathrm{lcm}(m,n) \mid |ab|$ by proving that $(ab)^{\mathrm{lcm}(m,n)} = e$. I know that it is ...
user avatar
  • 1,184
1 vote
1 answer
57 views

How to prove that the number 6𝑘+2 can be represented as the sum of two coprime numbers? [closed]

$k$ is a natural number. How can I prove that the number $6k+2$ can be represented as a sum of two coprime numbers? The greatest common divisor of two coprime numbers is $1$: For integers $m,n$, $\gcd(...
user avatar
  • 13
0 votes
0 answers
24 views

Proofs regarding gcd

I have two questions about proofs regarding gcd. We have $x^2+y^2+z^2=m^2$ with $x,y,z,m \in \mathbb{N}$. 1.) I want to show that, $gcd(x,y,m,z)=1$ is equivalent to $g(x,y,z)=1$ My attempt: The back ...
user avatar
0 votes
1 answer
32 views

Maximum number of colours we can use to colour all the integers so that for any integers i,j, i and j have the same colour if |i-j|=38 or |i-j|=27?

I tried solving this by plugging in a few smaller values for the differences, and it turns out that whenever the differences are coprime numbers, 1 colour is required. However, I couldn't construct ...
user avatar
1 vote
1 answer
83 views

Calculate $\gcd(a^2b^2, a^2 + ab + b^2)$ [duplicate]

Given $\gcd(a, b) = 1$, calculate $d =\gcd(a^2b^2, a^2 + ab + b^2)$ in terms of $a$ and $b$. I have tried some manipulations of the terms arriving to some expressions such as that $d$ divides $a^4 + b^...
user avatar
  • 129
6 votes
0 answers
223 views

When is the $\gcd$ not prime?

This is an extension of a previous question (Maximizing $\frac{\gcd(m,n)}{k}.$) which is interesting. Let $m=(p-1)^{p-1}+(p-1)!$ and let $n=((p-1)^{p-1}-(p-1)!)^{p-1}-1.$ For which odd primes is $\gcd(...
user avatar
0 votes
0 answers
73 views

On odd perfect numbers and a GCD - Part VIII

(This question is an offshoot of earlier posts with a similar title and this recent preprint.) Let $N = q^k n^2$ be an odd perfect number with special/Eulerian prime $q$ satisfying $q \equiv k \equiv ...
user avatar
0 votes
1 answer
92 views

how to find the number of integers between two numbers inclusive that are divisible by any of the two numbers X or Y. [closed]

You are given 4 integers X, Y, L, R. You need to find the number of integers between L and R inclusive that is divisible by any of the two numbers X or Y. How to find the answer without trying all ...
user avatar
2 votes
1 answer
52 views

Proof of Pythagorean quadruple [closed]

Given $x^2 + y^2 + z^2 = m^2$ with integers $x, y, z$ and $m > 0$, z odd and $(x,y,z)=1$. Set $x_{1}=\frac{1}{2}x$ and $y_{1}=\frac{1}{2}y$. Then $x_{1}^2+y_{1}^2=\frac{m+z}{2}\frac{m-z}{2}$. Set $...
user avatar
2 votes
1 answer
52 views

Is there a name for $\text{LCM}(a, n)/a$?

Unless I am mistaken, for any $a, n \in \mathbb N$ the following are equivalent: $\text{LCM}(a, n)/a$ The minimal $\ell \in \mathbb N$ such that $\underbrace{a + a + \cdots + a}_{\ell \text{ times}}$...
user avatar
  • 579
1 vote
4 answers
103 views

Calculate $\gcd(2a+4b, 2a +8b)$, if $a\equiv b \pmod{\! 5},\ 6a+11b = 5$

Given: $a$ is even $6a+11b=5$ $a-b=0\pmod 5$ Q: Calculate $\gcd(2a+4b,2a+8b)$ My try: We know there is some $i$ such that $a=2i$, plus from 3 we know there is some $j$ such that: $a-b=5j$ which ...
user avatar
  • 17
0 votes
2 answers
365 views

Does $\sigma(m^2)/p^k$ divide $m^2 - p^k$, if $p^k m^2$ is an odd perfect number with special prime $p$?

The following query is an offshoot of this post 1 and this post 2. Denote the classical sum of divisors of the positive integer $x$ by $\sigma(x)=\sigma_1(x)$. The topic of odd perfect numbers likely ...
user avatar
0 votes
1 answer
64 views

Finding the $\gcd$ of two polynomials over $\Bbb Z[x]$

I understand that there are other posts on the forum about the same topic, but, after reading them, I didn't understand exactly what to do in this situation. What I've done so far. In this same ...
user avatar
  • 601
0 votes
0 answers
26 views

How to reduce a triplet of integers into a triplet of pair-wise coprime integers?

A pair of integers $(x,y)$ can be reduced to a pair of coprime integers via $(x_1,y_1) = \left(\frac{x}{d},\frac{y}{d}\right)$ where $d = gcd(x,y).$ Suppose we have a triplet of integers $(x,y,z)$ and ...
user avatar
6 votes
0 answers
263 views

A singular variant of the OEIS sequence A349576

I refer to a previous post of mine in which it is defined the recurrence relation (now OEIS sequences A349576 and A349982) $$ x_{n+1} = \frac{x_{n} + x_{n-1}}{(x_{n},x_{n-1})} + c\;\;\;\;\;\;\;(1)$$ ...
user avatar

1
2 3 4 5
55