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.

Filter by
Sorted by
Tagged with
2
votes
1answer
64 views

(Strong) Duality for the integer programming for $\text{gcd}(c_1, c_2, \ldots, c_n)$

It is known that (quoted from CLRS, 3rd edition) If $a$ and $b$ are any integers, not both zero, then $\text{gcd}(a, b)$ is the smallest positive element of the set $\{ax + by: x, y \in \mathbb{Z}\}...
1
vote
1answer
44 views

Is there a commonly used term for a number divided by its greatest common divisor?

Does the expression $\frac{a}{\gcd(a, b)}$ have a common name? This type of expression occurs frequently in a program I'm writing. Since $ \forall a,b \in \mathbb{N^{*}}: \frac{a}{\gcd(a, b)} \perp \...
3
votes
1answer
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 ...
1
vote
2answers
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 ...
2
votes
2answers
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$....
1
vote
0answers
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 ...
2
votes
0answers
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] ...
2
votes
4answers
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 ...
-3
votes
1answer
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.
2
votes
1answer
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 ...
1
vote
0answers
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. ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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,...
0
votes
1answer
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 ...
-2
votes
2answers
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?
0
votes
1answer
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 ...
1
vote
1answer
73 views

Find all triplets $(a,b,c)$ less than or equal to 50 such that $a + b +c$ be divisible by $a$ and $b$ and $c$.

Find all triplets $(a,b,c)$ less than or equal to 50 such that $a + b +c$ be divisible by $a$ and $b$ and $c$.(i.e $a|a+b+c~~,~~b|a+b+c~~,~~c|a+b+c$) for example $(10,20,30)$ is a good triplet. ($10|...
0
votes
0answers
7 views

How to prove that the the number of buckets a hash function will fill is equal to n/gcf(n,k)

This question comes from computer science but its formality makes it inappropriate for asking in a programming environment. I've been rated down for asking non "programming-only" questions on there so ...
1
vote
1answer
101 views

Prove if there exists $[b]\in{Z}_{pq}$ such that $[b]^2=[a]$ in ${Z}_{pq}$, then there are exactly four distinct $[x]\in{Z}_{pq}$

Let $p$ and $q$ be distinct odd primes. Let $a\in{Z}$ with $gcd(a,pq)=1$. Prove that if there exists $[b]\in{Z}_{pq}$ such that $[b]^2=[a]$ in ${Z}_{pq}$, then there are exactly four distinct $[x]\in{...
-1
votes
1answer
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 ...
1
vote
1answer
83 views

Question about Modular Arithmetic

Let $q$ be an integer number. Consider an integer number $N$ such that $\gcd(q-1,N) = 1$. Question: How to show that if $q^d = 1 \pmod{N}$ for some positive integer $d$, then we get $$ 1 + q + q^2 + ...
5
votes
2answers
206 views

Can we invert these analogous “Dirichlet” series for GCD / LCM convolution?

We know that $\sum_{ab = n} f(a) g(b)$ is multiplicative in $n$ if $f, g$ are but what about $\sum_{\text{lcm}(a,b) = n} f(a) g(b)$. It associates because of associativity of $\text{lcm}$. Thanks @...
0
votes
2answers
38 views

Minimum no of bits to represent X [duplicate]

It took me much time to reach the solution where I find the value of X as 2 but still not sure whether this is correct or not. please help me with the solution
1
vote
0answers
31 views

Find the gcd$((a^{2^n})+1,(a^{2^m})+1)$ where $m,n$ are two distinct positive integers. [duplicate]

Let gcd$((a^{2^n})+1,(a^{2^m})+1)=d$. Then $d|(a^{2^n})+1$ and $d|(a^{2^m})+1$. So, $(a^{2^n})$ congruent to $(-1)$ (mod $d)$ and $(a^{2^m})$ congruent to $(-1)$ (mod $d).$ Let $m>n$ then $(m-n)&...
0
votes
3answers
58 views

Triangular numbers and gcd

For all positive integers $n$, the $n$th triangular number $T_n$ is defined as $T_n = 1+2+3+ \cdots + n$. What is the greatest possible value of the greatest common divisor of $4T_n$ and $n-1$? Can ...
0
votes
1answer
48 views

Sum on GCD and prime numbers

I was studying gcd then I encountered this sum $(1).$ A conjecture: If $(1)=1$ for any values of $N\ge3$, then N is a prime number. Let: $$f(N)=\frac{1}{N^{1-s}(N-1)}\sum_{j=1}^{N}(-1)^jj^s\frac{{...
1
vote
2answers
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 ...
1
vote
1answer
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....
5
votes
0answers
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 ...
-2
votes
1answer
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$.
-4
votes
1answer
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.
3
votes
3answers
114 views

GCD of cubic polynomials

I would appreciate some help finding $GCD(a^3-3ab^2, b^3-3ba^2)$; $a,b \in \mathbb{Z}$. So far I've got here: if $GCD(a,b)=d$ then $\exists \alpha, \beta$ so that $GCD(\alpha, \beta)=1$ and $\alpha d=...
1
vote
3answers
44 views

Let $a, b$ and $n$ be natural numbers. Prove that if $a^n$ and $b^n$ are relatively prime, then $a$ and $b$ are relatively prime.

Let $a, b$ and $n$ be natural numbers. Prove that if $a^n$ and $b^n$ are relatively prime, then $a$ and $b$ are relatively prime. I have been able to prove the above statement by contrapositive in ...
0
votes
1answer
194 views

What is $\gcd(61^{610}+1,61^{671}-1)$? [closed]

I implemented Extended Euclid Algorithm in c++ to solve this problem. Any approaches that you could it by hand. $\gcd(61^{610}+1,61^{671}-1)=\ ?$ Thanks in advance.
1
vote
0answers
14 views

Prove that there exists a $m×m$ lattice square in the $x-y$ plane such that none of its coordinates are visible [duplicate]

Call a lattice point 'visible' if the $gcd$ of its coordinates is 1. Then there exists a $m×m$ square in the $x-y$ plane such that none of its coordinates are visible. You can actually define such ...
2
votes
3answers
380 views

How to compute $\gcd(d^{\large 671}\! +\! 1, d^{\large 610}\! −\!1),\ d = \gcd(51^{\large 610}\! +\! 1, 51^{\large 671}\! −\!1)$

Let $(a,b)$ denote the greatest common divisor of $a$ and $b$. With $ \ d = (51^{\large 610}\! + 1,\, 51^{\large 671}\! −1)$ and $\ \ x \,=\, (d^{\large 671} + 1,\, \ d^{\large 610} −1 )$ find $\ ...
2
votes
2answers
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 ...
0
votes
2answers
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 ...
-1
votes
2answers
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 ...
5
votes
1answer
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$ ...
4
votes
2answers
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 ...
2
votes
1answer
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. ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
2answers
65 views

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$

No, this is not a duplicate of any thread. In fact, it is about a thread that I am still struggling to understand after all this time. I cannot comment on the thread because it was posted a very long ...
1
vote
1answer
61 views

A number theory question with calculus

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