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
-4 votes
1 answer
88 views

proof: If $a$ and $b$ are coprime if and only if $GCD(a,b)=1$ [closed]

In my college textbook, I came across this theorem: My first problem: Then, according to the fundamental theorem of algebra, $a$ and $b$ can be written unambiguously as the product of prime numbers ...
Omar's user avatar
  • 93
3 votes
2 answers
231 views

Interesting NT Question With AP and GCD.

Find the number of prime triplets $(p, q,r)$ such that $p(p + 1), q(q + 1),r(r + 1)$ form a strictly increasing arithmetic progression, where GCD $(r − p, 2p + 1)=1$. What I tried: $r(r+1)-p(p+1)=2d$ ...
CLASH ROYAL's user avatar
1 vote
0 answers
96 views

What $n$ would make $ \gcd _{k\ge1 }\left\{\dbinom{m+(k-1)\cdot n}{k}\right\}=1 \ \forall m \in \mathbb{N}$

This is a generalisation of this question. Construct the sequence $a_n$ $$ a_n = \begin{cases} 0, & \gcd _{k\ge1 }\left\{\dbinom{m+(k-1)\cdot n}{k}\right\}=1 \ \forall m \in \mathbb{N} \\ \min{m ...
pie's user avatar
  • 6,372
1 vote
0 answers
27 views

Conventional notation for gcd and principal ideal in the context of Bezout domain [duplicate]

Background Definition 1: Let $R$ be a commutative ring with identity, $c\in R$ and let $I$ be the set of all multiples of $c$ in $R$, that is, $I=\{rc\mid r\in R\}$. Set $I$ is an ideal and is ...
Seth's user avatar
  • 3,641
0 votes
0 answers
29 views

Slope and GCD points

given a slope in the form $y=ax+b$ My question is to know if there are (and if yes how to find them) points $(x,y)$ where : $gcd(x,y)>1$ (to be more precise, the $gcd$ is made between the $x$ and ...
Davinator's user avatar
4 votes
1 answer
122 views

On Prime, Lcm and Divisibility

Let $d_n= \text{lcm} \{1,2,3..., n \}$ then prove that for any prime $p$ $$ \left(\frac{1}{p^5-1}\right)\left(\frac{d_{p}}{p}\right)^5 \text{is not an integer}$$ Clearly $$\frac{d_p}{p}\in\mathbb{Z},...
Max's user avatar
  • 926
1 vote
2 answers
72 views

Expected number of factors of $LCM(1,…,n)$ (particularly, potentially, when $n=8t$)

I’m trying to prove something regarding $8t$-powersmooth numbers (a $k$-powersmooth number $n$ is one for which all prime powers $p^m$ such that $p^m|n$ are such that $p^m\le k$). Essentially, I have ...
Lieutenant Zipp's user avatar
0 votes
3 answers
110 views

$\gcd(\text{multiples}(a,b))= \text{lcm}(a, b)$?

I am exploring whether the following assertion holds true in integral domains: $\gcd(\text{multiples}(a,b))= \text{lcm}(a, b)$. Let us make this formal below. Consider two elements $a$ and $b$ in an ...
Martin Geller's user avatar
0 votes
1 answer
21 views

$f((x,y))=(x*gcd(x,y),y) $is injective and surjective?

The function $f:\mathbb{N^+}\times\mathbb{N^+} \rightarrow \mathbb{N^+}\times\mathbb{N^+} $ definide as $f((x,y))=(x*gcd(x,y),y) $is injective and surjective? Let $(a,b)\in\mathbb{N^+}\times\mathbb{N^+...
user1335731's user avatar
2 votes
1 answer
102 views

Question on LCM and divisibility

Let $d_n= \text{lcm} \{1,2,3..., n \}$ then for which natural numbers $n$ is $$\frac{24 d_n^5}{(n+1)^5} \text{not an integer?}$$ We know that $$ \text{lcm}\{1,2,3,...,n\}.\text{gcd}\{1,2,3,...,n\}=n!$...
Max's user avatar
  • 926
0 votes
2 answers
37 views

Velleman 6.4.17 - Stuck with proof involving GCD and divisibility

Level and context: I'm a first-year undergraduate self-studying proof writing from Velleman's How to Prove It (second edition). Exercise 17 (a). Suppose $a$, $b$, and $p$ are positive integers and $p$ ...
NikWantsToLearnMaths's user avatar
0 votes
0 answers
42 views

In $\Bbb Z[i]$ find $\gcd(2-7i,2+11i).$ Also find $x,y\in \Bbb Z[i]$ such that $(2-7i)x+(2+11i)y=\gcd(2-7i,2+11i).$ [duplicate]

In $\Bbb Z[i]$ find $\gcd(2-7i,2+11i).$ Also find $x,y\in \Bbb Z[i]$ such that $(2-7i)x+(2+11i)y=\gcd(2-7i,2+11i).$ I tried solving the problem as follows: Let $d=\gcd(2-7i,2+11i).$ So, $$d|2-7i,d|2+...
Thomas Finley's user avatar
3 votes
3 answers
167 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
0 votes
0 answers
36 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 vote
1 answer
55 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
466 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
  • 49.5k
1 vote
1 answer
84 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
365 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,726
0 votes
0 answers
58 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,726
4 votes
0 answers
34 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
  • 989
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
49 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
111 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
60 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
45 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
68 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
51 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 ...
SeekingAMathGeekGirlfriend's user avatar
0 votes
0 answers
31 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
  • 722
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,854
2 votes
1 answer
42 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
81 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,854
1 vote
2 answers
38 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,792
1 vote
0 answers
63 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
  • 49
7 votes
2 answers
491 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,531
2 votes
0 answers
96 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,190
0 votes
1 answer
84 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
51 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
  • 199
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
113 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
324 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
67 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
  • 385
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
111 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,761

1
2 3 4 5
55