Skip to main content

Questions tagged [gcd-and-lcm]

For questions related to gcd (greatest common divisor, also known as the hcf, the highest common factor), lcm (least common multiple), and related concepts from integer and ring theory.

Filter by
Sorted by
Tagged with
-1 votes
0 answers
21 views

Find an example that two elements can have different gcd in two rings [duplicate]

I have the following result now: $D$ is a PID and $D\subset R$ where $R$ is an integral domain. If $a,b\in D$, $d$ is the greatest common divisor of $a,b$ in $D$, then $d$ is also a greatest common ...
Zoe's user avatar
  • 1
3 votes
3 answers
146 views

Maximizing GCD of a variable set of numbers

Is there a systematic method of selecting a set of numbers (which add up to a constant total) in such a fashion as to maximizing their collective GCD? One example: select 5 different integers (greater ...
Steve237's user avatar
  • 187
-2 votes
0 answers
44 views

$k$ divide $2^k-1$, then $k=1$ [duplicate]

How to see that if $k$ is a natural number dividing $2^k-1$, then $k=1$? Using that $2^a-1$ divides $2^{ab}-1=(2^a)^b-1$ it can be easily reduced to case that $k$ is odd prime. But how to finish? I ...
user267839's user avatar
  • 7,139
0 votes
0 answers
33 views

Question about proof, using contrapositive, of Lamé’s theorem

Given the following lemma: If $a > b \geq 1$ and the call EUCLID(a, b) performs $k \geq 1$ recursive calls, then $a \geq F_{k+2}$ and $b \geq F_{k+1}$, which can be proved by induction, how is the ...
Hugh Mann's user avatar
-1 votes
0 answers
43 views

Explanation of why all the common factors are removed by dividing with their gcd [duplicate]

I understand the proof of this statement: If $\gcd(a, b) = d$, then $\gcd(a/d, b/d) = 1$. But I can't intuitively understand why this statement is true. I think it is because I don't understand why, ...
Classic's user avatar
1 vote
1 answer
53 views

Prove that the set of positive rational numbers is countable

While I was studying Discrete Mathematics, I faced a question that I do not understand how to solve even after looking at the answer. The question asks me to prove that the set of positive rational ...
Eric's user avatar
  • 145
2 votes
2 answers
184 views

Prove that if $\operatorname{lcm}(m,q)=\operatorname{lcm}(n,q)$, then $\operatorname{lcm}(m+n,q)\ge\operatorname{lcm}(n,q)$

Apart from changing $p$ to $q$, this is from an unanswered question that the OP deleted about a week ago. It asks to prove $$\operatorname{lcm}(m, q)=\operatorname{lcm}(n, q) \;\;\to\;\; \operatorname{...
John Omielan's user avatar
  • 48.8k
1 vote
1 answer
73 views

Bezout identity with relatively prime coefficients

The Bezout lemma says that given an ordered list of integers $x_1,\dotsc,x_n \in \mathbb Z$, one can find an associated list of coefficients $a_1,\dotsc,a_n \in \mathbb Z$ such that $a_1x_1+\dotsb+...
Ethan Dlugie's user avatar
  • 2,368
11 votes
2 answers
357 views

What is $\int_{0}^{\pi/2}\frac{\operatorname{lcm}(a\cos x,a\sin x)}{a^2}dx$?

I came up with this while messing around with the $\gcd$ and $\operatorname{lcm}$ functions in Desmos. $$I(a)=\int_{0}^{\pi/2}\frac{\operatorname{lcm}(a\cos x,a\sin x)}{a^2}dx$$ The function inside ...
Dylan Levine's user avatar
  • 1,676
0 votes
0 answers
55 views

How do you get GCD from an integral?

I was looking at this post and I am trying to reverse-engineer integrals that will have the $\gcd$ function in the solution. However, I am struggling to understand where the $\gcd$ actually comes from....
Dylan Levine's user avatar
  • 1,676
4 votes
0 answers
32 views

Upper bound on LCM of an arithmetic progression

Let $a$ be an even integer. I want to find a good upper bound on the least common multiple $L(a)$ of all elements in the set $\{a-1, 2a-1, 3a-1, \ldots, 2a^2-1\}$. A somewhat trivial bound can be ...
Woett's user avatar
  • 979
0 votes
0 answers
39 views

Show that $ \gcd(3\cdot2^n + 1, 2^{2n}- 3)$ is either $1$ or $13$. [duplicate]

Suppose that $d_n = \gcd(3\cdot2^n + 1, 2^{2n}- 3)$, where $n>0$. Show that $d_n$ is either $1$ or $13$. I tried to use the fact that $\gcd(a,b)=\gcd(a,a-b)$, but I couldn't go much further than ...
Diego Cândido's user avatar
1 vote
0 answers
48 views

Find the inverse of $1+x$ in the field $\mathbb{Q}[x]/(x^3-2)$. [duplicate]

I'm having trouble understanding the process behind the Extended Euclidean Algorithm. I know that $\mathbb{Q}[x]/(x^3-2)$ is a field with the greatest common divisor of $1+x$ and $x^3-2$ being 1 since ...
lambdaserb's user avatar
0 votes
0 answers
7 views

Getting the quotient $A/gcd(A,B)$ with the sub-resultant GCD algorithm

The sub-resultant GCD algorithm allows to get the GCD of two polynomials $A$ and $B$ with coefficients in a UFD. Is it possible with this algorithm to get the quotients $A / gcd(A,B)$ and $B / gcd(A, ...
Stéphane Laurent's user avatar
4 votes
1 answer
110 views

Minimal size of $a^2+b^2$ such that $ad-bc=1$

If $c,d$ are two relatively prime positive integers, then we can find integers $a,b$ such that $ad-bc=1$. But $a$ and $b$ are not unique: we can replace $a$ with $a+kc$ and $b$ with $b+kd$ for any ...
Math101's user avatar
  • 1,136
0 votes
1 answer
58 views

If $a$ and $b$ are coprimes in an euclidean domain, then $a^n$ and $b$ are coprimes. [duplicate]

Let $a,b\in\mathbb{E}$ where $\mathbb{E}$ is an euclidean domain. Prove that if $a$ and $b$ are coprimes, then $a^n$ and $b$ are coprimes for all $n\in\mathbb{N}$. I think the proof is by induction on ...
Angel Fernando Aviles Lopez's user avatar
1 vote
1 answer
59 views

A set $S$ of positive integers is self-indulgent if $\gcd(a, b) = |a-b|$ for any two distinct $a,b\in S$

A set $S$ of positive integers is self-indulgent if $\gcd(a, b) = |a-b|$ for any two distinct $a,b\in S$ (a) Prove that any self-indulgent set is finite. (b) Prove that for any positive integer n, ...
Swastik Sanyal's user avatar
-1 votes
1 answer
44 views

Find gcd of two multivariate polynomials [duplicate]

Is there a simple way to find the $\gcd$ of $x^2y$ and $xy^2+1$? I tried adding multiples of $x^2y$ to the other and vice-versa but I found no easy way to find the gcd. For another example I found $(...
Magne Seier's user avatar
2 votes
1 answer
67 views

How to prove that $\text{gcd}(a_1, a_2, ..., a_n) = \text{gcd}(a_1, a_1 + a_2, ..., a_1 + a_2 + ... + a_n)$ [duplicate]

How is it possible that $\text{gcd}(a_1, a_2, ..., a_n) = \text{gcd}(a_1, a_1 + a_2, ..., a_1 + a_2 + ... + a_n)$? This is not a homework or anything so an intuitive proof would be enough, but I can't ...
LinguiniThePasta's user avatar
0 votes
0 answers
48 views

General formula for factoring $ax^2+bx+c$ [duplicate]

I watched a YouTube video on factoring (namely, 100 trinomial factoring (Dedicated to Mr. Hill) by blackpenredpen) and was curious about the math behind the method he first shows around 12:15. Is ...
voltedz's user avatar
0 votes
0 answers
33 views

How to complete my proof on $a \mid c$, $b \mid c$ and $HCF(a,b)=1 \implies ab \mid c$ [duplicate]

How to complete my proof on $a \mid c$, $b \mid c$ and $HCF(a,b)=1 \implies ab \mid c$ My effort: Since $a,b$ both divides $c$, we have for some integers $m,n$ $$c=am,c=bn \implies c^2=abmn \implies ...
LifeIsMath's user avatar
2 votes
1 answer
95 views

Conjecture: $\forall n \geq n_0\exists k \geq 0: \gcd(2^k-1, \frac{p_n\#}{6}) = 1$.

Context & Interest. See this MSE post about a twin-prime related topology. Basically $0$ is a easily seen to be a generic point in this topology. Every generic point is clearly dense as a ...
HighAsAKiteOnMath's user avatar
0 votes
0 answers
30 views

factorization into coprimes subordinate to two given coprimes in GCD domain

Let $a,b,c$ be elements in a GCD domain (or just a GCD monoid) $R$. Suppose that $\text{gcd}(a,b)=1$ and $c \ne 0$. If $R$ is a UFD, it is possible to write $c=a'b'$ with $\text{gcd}(a',a)=\text{gcd}(...
Junyan Xu's user avatar
  • 712
0 votes
1 answer
24 views

Can we find an explicit formula for $r$ and $s$ as a function of $k$

Define $$g=\gcd(2^{k+3}-1,-2×(2^{k+1}-1)).$$ Then we know that there exist some integers $r$ and $s$ such that $$g=r×(2^{k+3}-1)-(2×s)(2^{k+1}-1).$$ Then my question is: Can we find an explicit ...
Safwane's user avatar
  • 3,830
0 votes
0 answers
23 views

reverse construction chinese remainder theorem

How can I determine the original number $x\in[pq]$ from its remainders $x_p$ and $x_q$, when it's divided by two relatively prime numbers $p$ and $q$, given that $\gcd(p, q) = 1$? I learned about a ...
Daniel Aviv's user avatar
0 votes
1 answer
80 views

Closed formula for a $gcd$ [closed]

Le $k≥1$ be positive integer. I am asking if it is possibe to find a closed formula for $$gcd(2^{2k+5}-3×2^{k+2}+1,2×(2^{k+2}-1)(2^{k+1}-1),2×(3×2^{k+1}-1)(2^{k+2}-1))$$ where $gcd$ is the greatest ...
Safwane's user avatar
  • 3,830
1 vote
2 answers
36 views

Least common multiple and greatest common divisor for monomial with rational coefficients

I have read in my textbook that if I have, for example two monomials $A$ e $B$ one or both with rational coefficients, $$A=\frac 34 x^2y^3, \qquad B=-2xyz$$ for the $\text{lcm}$ or the $\text{gcd}$ we ...
Sebastiano's user avatar
  • 7,725
1 vote
0 answers
62 views

Find the $\gcd(a^{2^m} + 1, a^{2^n} + 1)$ if $m>n$. [duplicate]

From what I know, the question can be solved from congruence modulo or without. Since the question is before the concept of congruence modulo in the book which I am using, I guess a solution without ...
1025's user avatar
  • 29
7 votes
2 answers
486 views

Solve $a+b=\gcd(a^3,b^3),\;b+c=\gcd(b^3,c^3),\;c+a=\gcd(c^3,a^3)$ for positive integers $a,b,c$

Solve $$\begin{cases}a+b=\gcd(a^3,b^3)\\ b+c=\gcd(b^3,c^3)\\ c+a=\gcd(c^3,a^3)\end{cases}$$ for positive integers $a,b,c$. We can rewrite as: $$\begin{cases}a+b=\gcd(a,b)^3\\ b+c=\gcd(b,c)^3\\ c+a=\...
Aig's user avatar
  • 5,521
1 vote
0 answers
92 views

Upper bounds on the greatest common divisor of sums of geometric series

Let $S_1=\sum_{i=0}^{n} p^i = \frac{p^{n+1}-1}{p-1}$ and $S_2=\sum_{i=0}^{m} q^i = \frac{q^{n+1}-1}{q-1}$ be two sums of geometric series, and $\gcd\left(S_1,S_2\right)$ its greatest common divisor. ...
Juan Moreno's user avatar
  • 1,110
0 votes
1 answer
82 views

Why can't we say, that any two elements in an arbitrary commutative ring with unit element has a greatest common divisor(gcd)? [duplicate]

While studying about the notion of gcd's in commutative rings, I came across a theorem which states that any two elements in a Euclidean Ring always have a gcd. While this is true, isn't this true for ...
Thomas Finley's user avatar
1 vote
1 answer
108 views

If for two strings a+b=b+a holds true, what properties can we derive about such strings? [duplicate]

Given two strings a and b such that a+b = b+a, what can we infer about such strings? Its ...
rachitiitr's user avatar
0 votes
1 answer
50 views

Proving membership of monomials to an ideal [closed]

I am a grad student having background in Algebra. I need help with the following. Let $I=\langle x_1^3,x_2^3,x_3^3,x_1 x_2 x_3,x_1^2 x_2^2, x_1^2 x_3^2, x_2^2 x_3^2 \rangle$ be an ideal in a ...
Raman's user avatar
  • 189
0 votes
0 answers
30 views

GCF of $A= 14a+4b$ and $B=11a+3b$ , with $a, b \in \mathbb Z$ and GCF$(a,b)= d$ [duplicate]

Source : Oudot, Maths MPSI , Hachette (ed.) ,exercice $6$, p. $195$. Let $a$ and $b$ be integers, and $d = $ GCF$(a,b)$. Let $A= 14a+4b$ and $B=11a+3b$. Question : determine GCF$(A,B)$. This is a ...
Vince Vickler's user avatar
0 votes
2 answers
86 views

Prove that $\gcd(a,b,c) = \gcd(\gcd(a,b),\gcd(a,c))$ [duplicate]

I have tried to prove this statement the following way: We will call $d_1=\gcd(a,b)$, $d_2=\gcd(a,c)$, $d=\gcd(d_1,d_2)$ and $D=\gcd(a,b,c)$. We know that: $d_1 \mid a$ and $d_1 \mid a$ $d_2 \mid a$ ...
Antonio De Angelis's user avatar
1 vote
2 answers
112 views

If $(a,b)=1$ and $n$ is a prime, prove that $ (a^n+b^n) /(a+b)$ and $(a+b)$ have no common factor, unless $a+b$ is a multiple of $n$

How do I solve this without using congruence modulo or Fermat's theorems. This problem is from a book called challenges and thrills of pre college mathematics, since this problems is from first ...
Yugant Shewale's user avatar
0 votes
1 answer
320 views

Confirmation of Equivalent Form of Riemann Hypothesis

Can anyone, who has knowledge of the following, share some more details about it because not much information is available publicly regarding the same: RH is equivalent to the assertion that for all $...
Ok-Virus2237's user avatar
1 vote
0 answers
32 views

Addition property for GCD [duplicate]

I already know that gcd(a,b)=gcd(a-b,b). However, can I also say that gcd(a,b)=gcd(a+b,b)? I think this is correct and the proof is simple: consider gcd(a+b,b). Then apply this subtraction property of ...
user124820929's user avatar
-1 votes
1 answer
65 views

If $b_1\mid a$ and $b_2\mid a$ and $\gcd(b_1,b_2)=1,$ show that $b_1b_2\mid a$. [duplicate]

I am trying to prove the following statement: if $b_1\mid a$ and $b_2\mid a$ and $\gcd(b_1,b_2)=1,$ show that $b_1b_2\mid a$. Well for starters we can write $a=b_1q_1$ and $a=b_2q_2$ for some $q_1,q_2\...
SAQ's user avatar
  • 365
0 votes
0 answers
34 views

If we have the Bezout coefficient, how to find the smallest possible coefficient that can take its place? [duplicate]

The question is the following: "Determine the pair of numbers m,n such that gcd(1234,5678)=1234⋅m+5678⋅n for which n is the smallest positive integer". I found that m=704 and n=-153. But n ...
Nare Avetisyan's user avatar
3 votes
3 answers
110 views

smallest child number

Problem : Let 'Child number' of positive integer $n$ be a positive integer that is divisible at least half of the factors of $n$. Find smallest 'Child number' of $21600$. My Attempt Since $$21600 = 2^...
bFur4list's user avatar
  • 2,751
3 votes
1 answer
153 views

GCD for three numbers (number theory)

For odd natural numbers $a,b,c$, prove that: $$\gcd \left( \frac{a+b}{2}, \frac{b+c}{2}, \frac{a+c}{2} \right) = \gcd(a, b, c).$$ How can we deal with the fact that: $$a = \frac{a + c}{2} + \frac{a + ...
Jacobs Monarch's user avatar
0 votes
0 answers
46 views

GCD and LCM of n Fractions – Proof of the Formulas [duplicate]

I need help proving the following two formulas: $$\gcd\left(\frac{a_1}{b_1}, \frac{a_2}{b_2}, \dots, \frac{a_n}{b_n}\right) = \frac{\gcd(a_1, a_2, \dots, a_n)}{\operatorname{lcm}(b_1, b_2, \dots, b_n)}...
Bolzano's user avatar
  • 81
0 votes
1 answer
77 views

Let $a,b,c,d \in\mathbb{Z}^+$. What are the minimal conditions required to state that $LCM(bcd, acd, abd, abc) = abcd$? How could I generalize it? [closed]

In the title you can see the question for the case $n = 4$, which was my original doubt. I couldn't prove that, couldn't even start on how to think about it. Also, it would be nice to know if that can ...
Italo Marinho's user avatar
1 vote
0 answers
41 views

Minimum perimeter of a triangle given certain number of dots on an cartesian plane

While experimenting with the polygon unction in desmos, I found a interesting problem. However, due to my lack of knowledge in analytic geometry I decided to summarize the problem here. This graph is ...
one stud cubed's user avatar
4 votes
1 answer
70 views

Modeling Nanotubes Geometry

In various references, we see the construction of unit cells of carbon nanotubes (CNTs) from chiral and translational vectors. The chiral vector is given as: $$\vec C_h = n\vec a_1 + m\vec a_2$$ ...
benjamin_ee's user avatar
  • 3,789
0 votes
0 answers
31 views

Halting condition in modular gcd algorithm

We consider the modular GCD-algorithm for $F[x, y]$. INPUT: $f, g \in F[x, y]$ primitive as polynomials in $F[y][x]$, with $\deg_x f \geq \deg_x g$; $d \in \mathbb{N}$ with $d \geq \deg_y(f), \deg_y(g)...
Magne Seier's user avatar
2 votes
2 answers
100 views

How can I find the periods of difference of the sine waves that has irrational coefficients

I'm working on a project right now. And now I need to find periods of difference of the sine waves and i'm stuck. In few resources I found that I can find the periods of summed or differenced sine ...
Eren Gümüş's user avatar
0 votes
1 answer
67 views

$a + b$, $b^{p - 1}$ coprime when $a$, $b$ coprime for odd prime $p$ [duplicate]

I was reading a proof of the theorem $$\gcd\bigg(\frac{a^p + b^p}{a + b}, a + b\bigg) \in \{1, p\}$$ where $a$, $b$ are coprime integers and $p$ is an odd prime. Using long division, we get $$\gcd(a + ...
aether's user avatar
  • 17
2 votes
2 answers
94 views

Prove by the Gauss lemma that if $a, b \in \mathbb{N} \Rightarrow $ the product $ab$ is equal to the multiplication of $GCD(a;b)$ with $LCM(a;b)$. [duplicate]

Question: Prove with the help of the Gauss lemma that if $a$ and $b$ are two integers then the product $ab$ is equal to the multiplication of $GCD(a;b)$ by $LCM(a;b)$. My attempt: 1- $GCD(a;b) = d \...
OffHakhol's user avatar
  • 717

1
2 3 4 5
54