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.
2,727
questions
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 ...
- 629
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 $\...
- 629
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+...
- 629
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)}$$
...
- 629
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)=...
- 629
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 ...
- 63
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$) ...
- 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 ...
- 21
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 ...
- 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 ...
- 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 ...
- 701
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\...
- 311
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 \...
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 ...
- 431
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 ...
- 431
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 ...
- 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 ...
- 41
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), (...
- 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))$$
- 1
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 \...
- 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,\...
- 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 () ...
- 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 ...
- 101
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}$$
...
- 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 ...
- 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(...
- 1,026
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}\...
- 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 ...
- 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 ...
- 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 $...
- 57
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 ...
- 1,349
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{...
- 57
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 ...
- 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 ...
- 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 ...
- 1,026
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 ...
- 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(...
- 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 ...
- 31
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 ...
- 23
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^...
- 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(...
- 562
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 ...
- 10.2k
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 ...
- 87
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 $...
- 31
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}}$...
- 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 ...
- 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 ...
- 10.2k
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 ...
- 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 ...
- 431
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)$$
...
- 1,806