# Questions tagged [gcd-and-lcm]

The concepts of *greatest common divisor* (which is also known as *Highest Common Factor*) and *least common multiple* are closely related notions in the integers, and also make sense in certain other rings. The tag is intended to encompass all questions related to these notions.

1,958 questions
Filter by
Sorted by
Tagged with
64 views

109 views

### Sums of the form $\sum\limits_{a_1=1}^n\sum\limits_{a_2=1}^{a_1}\cdots \sum\limits_{a_r=1}^{a_{r-1}}{[\gcd(a_1,a_2,\dots ,a_r)=1]}$

Background: Consider sums of the form $$\sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\cdots \sum_{a_r=1}^{a_{r-1}}{[\gcd(a_1,a_2,\dots ,a_r)=1]},$$ with $[\gcd(a_1,a_2,\dots ,a_r)=1]$ being equal to $1$ if the ...
47 views

### Finding all pairs of integers satisfying gcd(a,b) = 6 and lcm(a,b)=540 [duplicate]

Given that $$a\cdot b=gcd(a,b)\cdot lcm(a,b)$$ How can we find all the integer solutions $(a,b)$ if $gcd(a,b)=6$ and $lcm(a,b)=540$? The first thing I did was factorizing using the fundamental ...
89 views

### Non-Separable Polynomials and their Derivatives

We say that a polynomial $f(x) ∈ F[x]$ is inseparable if it has a repeated root in some field extension. Otherwise we say that $f(x)$ is separable. Prove that $f(x)$ is separable $\iff\gcd(f, Df) = 1$....
42 views

### If $(m, n) = 1$, then $\dfrac{\mathbb Z \times \mathbb Z}{\langle (m,n)\rangle}\cong\mathbb Z$

How to show that If $(m, n) = 1$, then $\dfrac{\mathbb Z \times \mathbb Z}{\langle (m,n)\rangle}\cong\mathbb Z$. (Note: We consider this in group theory.) I know that $(m, n) = 1$ means that ...
61 views

### Find minimum GCD of a pair of elements in an array

Given an list of elements, I have to find the MINIMUM GCD possible between any two pairs of the array in least time complexity. Example Input list=[7,3,14,9,6] ...
408 views

### LCM of even and odd integers

Is the least common multiple of an even $2k$ and odd number $2l+1$ always the product of both numbers $2k(2l+1)$ ? And also is the least common multiples of two odd numbers the product of both odd ...
87 views

### How to calculate the gcd of (3^{100!}-1,116)? [closed]

I have to find out the result of $$(3^{100!}-1,116)$$ This is an exercise after the chapter of integer factorization and now I need help.
62 views

### Niho APN prove that $gcd(d − 1, 2^n − 1)$ , where d is exponent

in a finite field $F_{2^n}$ where $d = \begin{cases} 2^t + 2^{t/2}-1 & \text{t even}\\ 2^t + 2^{(3t+1)/2}-1 & \text{t odd} \end{cases}$ and $n=2t+1$ How do you prove ...
72 views

### Proof by induction $\gcd(2^n-1,2^m-1)=2^{\gcd(n,m)}-1$

It is asked to perform a proof by induction over a variable $k$, which is $k=m+n$ and to use a given equation: $\gcd(a,b)=\gcd(a+b,b)=\gcd(ac+b,a)$, which might help throughout the proof-writing. ...
47 views

### Find $\theta\in [0,2\pi]$ if $\theta = \frac{n\pi}{2}$ and $\theta = \frac{2m\pi}{5} + \frac{\pi}{10}$, where $n,m$ are integers

$\theta = \dfrac{n\pi}{2}$ and $\theta = \dfrac{2m\pi}{5} + \dfrac{\pi}{10}$ where $n ,m \in \mathbb Z$. Find $\theta\in [0,2\pi]$. It can be solved by hit and try, of course but is there any ...
26 views

### Induction proof for gcd(a,b), and s, t

Show that if a ≥ b > 0, and gcd(a,b)=d, and as+bt=d, then the values s and t satisfy: |s| ≤ b/d and |t| ≤ a/d Hint: prove by induction on b: be careful, you have to stop the induction before b gets to ...
52 views

### If $\gcd(a,b)=1$ then $\gcd(a^n,b^n)=1$ [duplicate]

I wanted to use mathematical induction. So if $n=1$ then $\gcd(a^1,b^1)=1=\gcd(a,b)$ is true. Then I assumed $n=k$ then $\gcd(a^k,b^k)=1$ is true. At this part I need to show that $n=k+1$ is also true,...
66 views

### How many marbles?

One dozen of big marbles and small marbles is 132 gram. If one big marbles is 3 gram heavier than one small marbles, then specify the possibilities of how many are the big marbles and the small ...
41 views

### gcd between powers of two co-prime numbers [duplicate]

Is it true that $\forall x,y,n\in \mathbb{Z}$, if $\gcd(x,y)=1$ then $\gcd(x^n, y)=1$? If not, is there a counterexample?
37 views

### Pirate and Bags of Coin

A pirate captain has 63 bags of coin with the same amount of coin inside each of the bags. If he wants to divided the coins to his 23 henchman evenly, he has to add 7 more coins. How many coins inside ...
73 views

68 views

### Is it true that (k,n+k)=d if and only if (k,n)=d? [duplicate]

Is it true that (k,n+k)=d if and only if (k,n)=d? I solved "Prove that (k,n+k)=1 if and only if (k,n)=1" but I cannot solve "Is it true that (k,n+k)=d if and only if (k,n)=d?" I think it is False ...
83 views

81 views

### Prove that if there are integers $m$ and $n$ such that $am +bn =1$ then $a$ and $b$ are coprime.

Suppose $a,b \in \mathbb{N}$. Prove that if there are integers $m$ and $n$ such that $am +bn =1$ then $a$ and $b$ are coprime. I came up with the following proof, but I am sure a shorter argument ...
41 views

### How to prove that if $(ab,n)=1$ then, $(r,n)=1$? [duplicate]

Let $ab=nq+r$ where all variables represent integers with $0\leq r<n$. If $(ab,n)=1$ then how to prove that $(r,n)=1$? I need to prove this to help me understand the proof of Euler's theorem better....
101 views

### Conjecture about primes and the greatest common divisor

Conjecture: Given $m,n\in\mathbb N^+$, one odd and one even, there are two primes $p,q$ such that $|mp-nq|=\gcd(m,n)$. I hope MSE can determine its validity. From time to time, when testing my ...
80 views

### Prove gcd(n, n+m) divides m [closed]

The question asks me to use mathematical language to prove that: $\gcd(n, n+m)$ divides $m$.
49 views

### Prove $\gcd(2a,2b+1)=\gcd(a,2b+1)$

Let $a,b\in\Bbb Z$. $\gcd(2a,2b+1)=\gcd(a,2b+1)$ If $a\ge b,\gcd(2a+1, 2b+1) =\gcd(2a+1,2a-2b) =\gcd(2a+1,a-b)$ Please prove these two things.
114 views

121 views

### Suppose that $T$ is the smallest positive integer satisfying $m^{T}\equiv \pmod {pq}$. Prove that $T\mid(p-1)(q-1)$.

Suppose that $p$ and $q$ are distinct primes and that $m$ is an integer satisfying $\gcd(m, pq) = 1$. Suppose that $T$ is the smallest positive integer satisfying $m^{T}\equiv \pmod {pq}$. Prove ...
26 views

### Is it possible to find a multiple knowing only: the count of its divisors, the upper limit and some of its divisors (more details)?

In other words, say I am looking for multiple X let: X < 1000005 let the fist 18 divisors of X be: 1 | 2 | 4 | 5 | 8 | 10 | 16 | 20 | 25 | 32 | 40 | 50 | 64 | 80 | 100 | 125 | 160 | 200 ...
55 views

### Prove that the sum is not an integer

Prove that if a / b and c / d are two irreducible rational numbers such that gcd (b, d) = 1 then the sum (a/b + c/d) is not an integer. I was thinking about the proof by contradiction, but then I ...
61 views

### Lower Bound on the Sum of Reciprocal of LCM

While reading online, I encountered this post which the author claims that \begin{align} S(N, 1):=\sum_{1\le i, j \le N} \frac{1}{\text{lcm}(i, j)} \geq 3H_N-2 \end{align} and $S(N, 1) \geq H_N^2$ ...
84 views

### About the limit $\lim_{n \to +\infty} \frac{1}{n^2} \sum_{1 \le a,b \le n} \frac{1}{ \mathrm{gcd} (a,b)}$

This is not homework. My question is: Prove or disprove: $$\lim_{n \to +\infty} \frac{1}{n^2} \sum_{a,b=1}^n \frac{1}{ \mathrm{gcd} (a,b)} = \frac{\zeta(3)}{\zeta(2)}$$ This would represent the ...
46 views

### How to derive the relation between $k$ and $l$ given $\langle g^k \rangle = \langle g^l \rangle$ in a cyclic group $C_n = \langle g \rangle$?

It is known that For a cyclic group $C_n = \langle g \rangle$ of order $n$, we have $\langle g^k \rangle = \langle g^{(k, n)} \rangle$, where $k \in \mathbb{Z}$. I am able to verify this result. ...
26 views

### $\gcd$ and $\text{lcm}$ of more than $2$ positive integers [duplicate]

For any two positive integers ${n_1,n_2}$, the relationship between their greatest common divisor and their least common multiple is given by $$\text{lcm}(n_1,n_2)=\frac{n_1 n_2}{\gcd(n_1,n_2)}$$ If ...
29 views

### How is the process of reducing the fraction down to zero almost exactly the same as finding the greatest common divisor?

Professor Sir Tom Davis in a note - Conway's Rational Tangles has said $$\\$$ If the students are a bit advanced, you can point out that the process of reducing the fraction down to zero is almost ...
### How does the Euclidean Algorithm apply on exponents m and n to show that $gcd(p^m-1, p^n-1) = p^{gcd(m,n)}-1$
Let $P(x)\in \mathbb{R}[x]$ Show there exists a non-constant polynomial $m(x)$ such that $m^2(x)|P(x)$ iff gcd$(P(x),P'(x))$ is not $1$. My attempt: if $m^2(x)|P(x)$ then $m(x)|gcd(P(x),P'(x))$. So ...