# 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.

2,700 questions
Filter by
Sorted by
Tagged with
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 ...
• 1
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 ...
• 187
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 ...
• 7,139
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 ...
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, ...
1 vote
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 ...
• 145
184 views

• 115
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 ...
• 21.5k
30 views

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 ...
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 + ...
• 17
### 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 \...