All Questions
Tagged with greatest-common-divisor or gcd-and-lcm
3,138 questions
8
votes
3
answers
284
views
Why is there no Euclidean Algorithm for the least common multiple (lcm)?
The greatest common divisor (gcd) of two integers $a$ and $b$ can be computed with the Euclidean Algorithm.
With the gcd known, one can compute the least common multiple (lcm) via the formula $\mathrm{...
- 741
2
votes
1
answer
99
views
Does any infinite set of elements in a GCD Domain have a GCD?
I know this holds in a UFD, since we can choose an element $a$ for any subset of it, the common divisors are also divisors of $a$ and then there are at most a finite number of them, so there is a ...
23
votes
1
answer
2k
views
Continuous extensions of GCD to $\Bbb R^{+}\!\!\times \Bbb R^{+}\!$ still commutative and distributive
Question. Is there an extension of the GCD function? Since the concept of divisibility breaks down in $\mathbb{R}$, is there an established analytic interpretation of $\gcd(m, n)$ for non-integer ...
- 5,309
6
votes
4
answers
428
views
Least $n$ with ${\rm lcm}(n,20,15) = 360$ [duplicate]
Three bus lines, $A$, $B$, and $C$, depart from the terminal. Departures start simultaneously at 6:30 AM.
Bus line $A$ returns to the terminal every 25 minutes, line $B$ every 20 minutes, and line $C$ ...
- 8,896
9
votes
1
answer
700
views
A riddle involving the difference between lcm and GCD
I just read this riddle which i find quite interesting:
Two friends are staying at the same hotel. While chatting in the lobby, one says to the other: "The difference between the least common ...
- 189
3
votes
1
answer
119
views
The minimum of maximal value of a gcd-related function in an integer sequence
Given $n$ distinct positive integers $a_1,\dots,a_n$, does there always exist $i,j$ such that $\frac{a_i}{\gcd(a_i,a_j)}\geq n$?
(It is not hard to see that when $a_i=i$, the maximal value of $\frac{...
- 866
1
vote
0
answers
33
views
what is the minimum number of video frames to have a clean loop for a song with a particular tempo? [duplicate]
It occurred to me to ask this question of the video SE community, but I worry about their mathematical prowess, and I'm looking for a really clean formula or algorithm for this problem.
I have a song ...
- 111
3
votes
0
answers
509
views
Is $11$ the largest value of $p$ such that $\gcd(2^{p}-1, \lfloor\sqrt{2^{p}}\rfloor^{2}-1)\neq1$, where $p$ is a prime number?
Question: Is $11$ the largest value of $p$ such that $\gcd(2^{p}-1, \lfloor\sqrt{2^{p}}\rfloor^{2}-1)\neq1$, where $p$ is a prime number?
I know that $p=11$ is the least value of $p$ such that $2^{11}-...
- 1,026
2
votes
1
answer
120
views
For $a_n = \sum_ {k=1} ^{n-1} \gcd(n, a_k) $ Prove that $a_{n+1} \leq a_n$ infinitely often. [closed]
$a_1 \in \mathbb N$ arbitrary. I got above question from a Youtube Video. It seems to stem from some (earlier) math competition and the Indices might have been slightly shifted (though i feel like ...
- 1,586
0
votes
0
answers
108
views
A hidden modular order in a bizarre recurrence involving gcd
Let’s play with the recurrence (see also this post of mine)
$$x_{n+1} = \frac{x_n + x_{n-1}}{\gcd(x_n + x_0x_1,\; x_n + x_{n-1})},
\qquad (x_0, x_1)\in\mathbb Z^2.$$
At first sight it looks chaotic: ...
- 3,054
0
votes
3
answers
172
views
Show that if $d = \gcd(a, b)$, $a \mid b$, and $c \mid b$, then $ac \mid bd$. [duplicate]
I need help in proving if $d = \gcd(a, b)$, $a \mid b$, and $c \mid b$, then $ac \mid bd$.
There is a similar question but the key difference is that $d = \gcd(a, b)$ and not $d = \gcd(a, c)$.
I think ...
- 27
3
votes
0
answers
119
views
Conjecture on upper bound for sum of $\sum_{a \in S} 1/a$ for $S$ satisfy $\mathrm{lcm}(a,b) > n$ for every $a \neq b \in S$
Recently I found an interesting problem on number theory which stated
For a set $S$ of integers ranging from $1$ to $n$ such that for every $a\neq b,~a,b \in S$ we have that $\mathrm{lcm}(a,b) > n$...
- 333
2
votes
1
answer
149
views
Using GCD to Prove Pick's Theorem
I recently posted a related question at Using GCF to Prove Pick's Theorem, but I accidentally intended the converse. Instead of revising a mostly coherent post, I'm making a new one with the backstory ...
- 730
3
votes
2
answers
110
views
Using GCF To Prove Pick's Theorem [duplicate]
I am teaching high school geometry and I'm building between Euclid's number theory and his geometry. I want to prove Euler's formula in multiple ways, for much the same reason that Bonnie Stewart ...
- 730
0
votes
1
answer
164
views
Polynomial GCD convention for over $\Bbb Z$ vs. over $\Bbb Q$
This year, I have been assigned to teach a very particular second-year class of 14/15-year-old students, of an high secondary school.
In an entrance test, when you want to calculate the $\operatorname{...
- 8,896