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
0
votes
1answer
19 views

Proving an equality using Euler Totient function [duplicate]

$ϕ(m · n) = \frac{ϕ(m) · ϕ(n) · gcd(m, n)}{ϕ(gcd(m, n))}$ Deduce from the previous identity that $ϕ(n^k) = n^{k−1}· ϕ(n)$ I know that \begin{eqnarray*} \phi(m) = m \prod_{p \mid m } (1-\frac{1}{...
0
votes
1answer
34 views

gcd as linear combination [on hold]

I am trying to prove the following statement: Let $y > x \geq 1, x, y \in \mathbb{Z}$. Then there exists $u, w \in \mathbb{Z}$ with $0 \leq u \leq y-1$ and $0 \leq w \leq x-1$ such that $xu - yw = ...
0
votes
0answers
21 views

Using Euler's Totient identity to deduce an equality

$ϕ(m · n) = \frac{ϕ(m) · ϕ(n) · gcd(m, n)}{ϕ(gcd(m, n))}$ Deduce from the previous identity that $ϕ(n^k) = n^{k−1}· ϕ(n)$ I know that \begin{eqnarray*} \phi(m) = m \prod_{p \mid m } (1-\frac{1}{p}). ...
1
vote
1answer
44 views

Using Euler Totient Function to prove an identity

Show the following identity for Euler’s ϕ function: $ϕ(m · n) = \frac{ϕ(m) · ϕ(n) · gcd(m, n)}{ϕ(gcd(m, n))}$ \begin{eqnarray*} \phi(m) = m \prod_{p \mid m } (1-\frac{1}{p}). \\ \end{eqnarray*} ...
1
vote
1answer
47 views

Let $(G, \cdot)$ be an abelian group, and $g, h\in G$ have orders $a$ and $b$ respectively. What can you say about $(gh)^{ax_0}$?

Let $a, b\in\mathbb Z$, and assume that $\gcd(a,b)=1$. a) Show that there exist $x_0$, $y_0\in\mathbb Z$ such that $ax_0 + by_0 = 1$. b) Suppose $m\in\mathbb Z$ and $a\mid bm$. Show that $a\...
5
votes
5answers
55 views

Is $\gcd(x+y, xy)-\gcd(x, y)$ an even or odd number?

Let's say $d=\gcd(x, y)$ I realize that $d$ is a common divisor of $x+y$ and $xy$, and their greatest common divisor would be some multiple of $d$, let's say $kd$. So $$\gcd(x+y, xy)-\gcd(x, y)=kd-d=...
3
votes
4answers
89 views

Least positive solution of $ax = by$ is $(x,y) = (b/d,a/d),\ d = \gcd(a,b)$

Let $a,b$ be positive integers. Suppose that $x,y$ are the smallest positive integers such that $ax-by = 0$. Prove that \begin{align*} x = \dfrac{b}{gcd(a,b)} \quad \text{and} \quad y = \...
2
votes
2answers
58 views

Let $a,b,c,r,s\in\mathbb{Z}$ such that $(a,b)=r$, $(a,c)=s$ and $(b,c)=1$. Prove that $(a,bc)=rs$.

Let $a,b,c,r,s\in\mathbb{Z}$ such that $(a,b)=r$, $(a,c)=s$ and $(b,c)=1$. Prove that $(a,bc)=rs$. Proof: $ax_1+by_1=r$ and $ax_2+cy_2=s$ for some $x_i\in\mathbb{Z}$. This gives \begin{align*} by_1=...
1
vote
1answer
45 views

Nontrivial Bezout Sums

Given $x_1, \ldots , x_n \in \mathbb{Z}$ with $\gcd (x_1, \ldots, x_n) = d$, I'll call any sum of the form $$ \sum_{i = 1}^n x_i y_i = d $$ with $y_1, \ldots, y_n \in \mathbb{Z}$ a Bezout sum. For ...
0
votes
0answers
26 views

gcd is min of exponents of prime numbers [duplicate]

$n, m$ ∈ $\mathbb N^+$. We decompose them as products of prime numbers $n = p_1^{k_1}· · · p_R^{k_R}$ $m = p_1^{l_1}· · · p_R^{l_R}$ where $k_1, . . . , k_R$, $l_1, . . . l_R$ ∈ $\...
-1
votes
1answer
28 views

Can any one can tell about calculating gcd(pow(a,b),n) fast without calculating pow(a,b) [closed]

The values are large enough to take time by gmpy2
0
votes
0answers
28 views

Show $a_1 \mathbb Z$ ∩ $a_2 \mathbb Z$ = $N \mathbb Z$ [duplicate]

Let $a_1$, $a_2$ ∈ $\mathbb Z$ and let $N$ = lcm($a_1$, $a_2$). Show $a_1 \mathbb Z$ ∩ $a_2 \mathbb Z$ = $N \mathbb Z$ where $c \mathbb Z$ = {$c · n : n$ ∈ $\mathbb Z$}. My attempt: ...
1
vote
1answer
34 views

Proving equivalence of formal definition of $\gcd$ with the usual definition of $\gcd$ in $\mathbb Z$

I know that the definition of gcd of two numbers $ a, b $ is $G$ ,where $G\mid a$, $\;G\mid b $ and If $d\mid a$, $\;d\mid b $, then $ d\mid G.$ Now, using this how do I prove that in $\mathbb Z$, ...
3
votes
2answers
40 views

Find the smallest whole number..

This question is related to prime factorisation. How do I find the smallest whole number $b$ for which $240/b$ is a factor of $252$? \begin{align*} 240 &= 2^4 \times 3 \times 5 \\ 252 &= 2^2 ...
3
votes
5answers
64 views

GCD property: $b\mid ac$ implies $b\mid (a,b)(b,c)$

The following is a very simple statement I want to prove: If $a,b,c$ are non-zero integers, then $b\mid ac$ implies $b\mid (a,b)(b,c)$ Here $(a,b),[a,b]$ denote the greatest common divisor and the ...
0
votes
0answers
62 views

How efficient can a factoring method using only GCD calculations be?

This post was inspired by the following one. Fast way to check if two integers don't have any prime factors in common We consider the sequence of numbers of equal $(p+q)$ for a number $N=pq$. ...
2
votes
0answers
21 views

Order of a sum of elements in an abelian group [duplicate]

We need to prove the following statement: Let $A$ be an abelian group, $x_1,\dots,x_h \in A$ and let $q_1,\dots,q_h$ be prime numbers. Suppose that, for all $1 \leq i \leq h$, there exists $k_i \in ...
1
vote
2answers
54 views

Prove the sum of two rational number is equal to $\frac{e}{lcm(b,d)}$ for some integer $e$.

As title state: $\frac{a}{b} + \frac{c}{d}=\frac{e}{lcm(b,d)}$ for some integer $e$. Here is what I tried: $\frac{a}{b} + \frac{c}{d} = \frac{ad+bc}{bd}$ Since $gcd(b,d)lcm(b,d)=bd$, so I got $\...
4
votes
0answers
31 views

Subgroup of multiples of $m$, $m$-torsion and $p$-subgroup of $\mathbb{Z}_n$

Disclaimer: this terminology might be different from what you're used to and this is why I'm writing down some definitions first. Let $A$ be an abelian group, $m \in \mathbb{N}^* := \mathbb{N} \...
0
votes
1answer
27 views

Help with proof gcd and modular arithmetic [duplicate]

Let $a, b ,n \in Z$ with $n > 0$ and $a \equiv b \pmod n$. Show that $\gcd(a,n) = \gcd(b,n) = d$. I tried rewriting $b = a + ny$ for some $y \in Z$. Now if I have $d \mid a$ and $d \mid n$, then $...
0
votes
1answer
36 views

GCD Euclidean algorithm x WolframAlpha [duplicate]

I was given the following exercise: Find the gcd of $x^4+x^3+2x^2+x+1 $ and $x^3+4x^2+4x+3 $ in $\mathbb{Q}[x]$ using the Euclidean algorithm. Well, I used the Euclidean algorithm and got $10x^2+...
-1
votes
2answers
77 views

What is lcm($2^n,3^m$)?

Given $n,m\in\mathbb{N}$, what can be said about $\text{lcm}(2^n,3^m)$? In general, for $a,b\in\mathbb{N}$, is there a closed formula of $\text{lcm}(a^n,b^m)$?
2
votes
1answer
81 views

Fast way to check if two integers don't have any prime factors in common

I would like to know if two integers $a$ and $b$ have at least one prime factor in common. I know calculating the GCD (by e.g. the Euclidean algorithm) would produce the right answer. However since I ...
1
vote
2answers
47 views

Prove that $\gcd(a,b) = \gcd(b, r) \neq \gcd(a, r)$ where $r$ is the remainder of dividing $a$ by $b$

I can't found an explanation on why $\gcd(a,b) \neq \gcd(a, r)$, where $r$ is the remainder of dividing $b$ by $a$ I set $r = a - bq$, so if $d \mid a$ and $d \mid b$ then $d \mid r$. If now I set $...
4
votes
3answers
63 views

What is GCD of $7^{3001}-1$ and $7^{3000}+1$?

Find GCD of $7^{3001}-1$ and $7^{3000}+1$. My work. I noted that $(1)(7^{3001}-1) -(7)(7^{3000}+1)=-8$.
7
votes
1answer
122 views

Asymptotic behavior of number of triples $i,j,k\le n$ with pairwise bounded least common multiples each $\le n$.

I want to know a tighter bound for the growth rate of $f(n)$ when $n\to\infty $, where $$ f(n)=\sum_{i=1}^n\sum_{j=i}^n\sum_{k=j}^n [\mathrm{lcm}(i,j)\le n][\mathrm{lcm}(j,k)\le n][\mathrm{lcm}(i,k)...
1
vote
1answer
18 views

Divisors of every integer in a set

Let $S$ be the set of all positive integers $n$ s.t. $n^2$ is a multiple of both $24$ and $108$. Which of the following integers are divisors of every integer $n$ in $S$? Attempt: $n^2=24k \wedge ...
0
votes
2answers
33 views

Divisibility proof with coprimes of 6 [duplicate]

I asked this question earlier and asked people to not tell me the answer. After a few more hours of attempts, I cannot figure this out. Can someone please tell me how to solve this proof? Suppose $(6,...
4
votes
3answers
75 views

How would you prove if $ab|(a+b)(a+b+1)$, then $(a,b) \leq \sqrt{a+b}$ for positive integers $a$ and $b$?

How would you prove if $ab|(a+b)(a+b+1)$, then $(a,b) \leq \sqrt{a+b}$ for positive integers $a$ and $b$? My thoughts: I tried squaring both sides of $(a,b) \leq \sqrt{a+b}$ but don't know what to do ...
13
votes
1answer
154 views

Failure of existence of GCD

In all the examples I've seen of $\gcd(a, b)$ not existing (e.g. MO, Wiki), the poset of principal ideals containing $(a, b)$ is finite but has more than one minimal element. Are other modes of ...
5
votes
2answers
69 views

Divisibility proof for numbers coprime to $6$

Can someone check on this? If it is wrong please refrain from telling me the answer. Suppose $(6,a) = (6,b) = 1$. We wish to prove $24 \mid (a^2-b^2)$. We can see that $(4,a) = (4,b) = 1$ since $2 \...
4
votes
1answer
66 views

Prove that $n!=\prod_{k=1}^n \operatorname{lcm}(1,2,…,\lfloor n/k \rfloor)$ for any $n \in \mathbb N$

I try to prove the following formula: $$n!=\prod_{k=1}^n \operatorname{lcm}(1,2,...,\lfloor n/k \rfloor)$$ I noticed that $\upsilon_{p}(\operatorname{lcm}(1,2,...,\lfloor n/k \rfloor)) = s$ iff $\...
3
votes
3answers
97 views

Find $\gcd(5^{300} - 1, 5^{200} + 6)$

Find $\gcd(5^{300} - 1, 5^{200} + 6)$ In this question I tried using Euclid Algorithm but got scared that I may have done a mistake. Wolfram Alpha says that the answer is $31$ but I don't know how to ...
2
votes
1answer
32 views

Greatest Common Divisor in pair of cycles

In this answer, the author says each block of $n\times m$ elements is split into $\gcd(m,n)$ distinct cycles. This seems nontrivial, how is this proven?
1
vote
2answers
40 views

Number of ways to divide a set of numbers in 2 sets such that the GCD of their product is 1? [closed]

Given any set of positive integers, I am trying to figure out a way to divide the set into 2-parts such that the gcd(greatest common divisor) of the product of the 2 sets is 1. Example set :- {2,3,...
0
votes
2answers
37 views

Why does ab = nc +1 mean the same as ab $\equiv$ 1 (mod n)?

Why does ab = nc +1 mean the same as ab $\equiv$ 1 (mod n)? Is it enough to say that since ab = nc + 1 then ab mod n = 1? Or do we need further steps to clarify?
0
votes
0answers
23 views

gcd (m/gcd (m,n), n/gcd (m,n)) [duplicate]

there is a theory that I came across in a textbook n and m are positive integers let a = n / gcd (m, n) let b = m / gcd (m, n) then, gcd (a, b) = 1 but it is with no proof
0
votes
0answers
43 views

To prove $\gcd\{p^2-1: p $ is a prime $ \geq 7 \}=24$ [duplicate]

Let $p$ be a prime $\geq 7$. $p^2-1=(p+1)(p-1)$. Both $(p-1)$ and $(p+1)$ are divisible by $2$ and they are two consecutive even numbers. So, either one of the two must be divisible by $4$. So, $8 \...
0
votes
2answers
52 views

$\sum_{i=1}^{n} GCD(i + 1, 2)$

I need to calculate the following sum: $$S_{n} = \sum_{i=1}^{n} GCD(i + 1, 2)$$ where $GCD(x,y)$ stands for greatest common divisor of $x$ and $y$. The terms of this sum simply boil down to: $$\...
1
vote
0answers
43 views

Special cases when $\deg(\gcd(f,g)) \in \{0,1\}$

Let $k$ be a field of characteristic zero. Let $f=f(t), g=g(t) \in k[t]$ and assume that $\deg(f)=dn$, $\deg(g)=dm$, where $d=\gcd(\deg(f),\deg(g)) \geq 2$, $\gcd(n,m)=1$ and $n < m$. Then we can ...
0
votes
2answers
26 views

GCD expressed with irreducible elements in a unique factorization domain

Let $R$ be a unique factorization domain (UFD). Given $a,b \in R$ not simultaneously equal to zero, an element $d \in R$ is by definition a greatest common divisor (GCD) of $a$ and $b$ provided: $d \...
2
votes
0answers
45 views

partition that maximizes lcm

Let $n$ be a natural number. How can I find a partition of $n$ such that its least common multiple is maximized? In other words, how can I find $a_1, a_2, \cdots a_m \in \mathbb{N}$ such that $$a_1 + ...
0
votes
1answer
32 views

GCD of {0} in integral domains

Quoting Hungerford's Algebra: A nonzero element $a$ of a commutative ring $R$ is said to divide an element $b \in R$ (notation: $a \mid b$) if there exists $x \in R$ such that $ax = b$. Let $X$...
7
votes
2answers
170 views

Find the greatest common divisor of $2^m+1$ and $2^n+1$ that $m,n$ are positive integers.

I am confused of a question that needs to know the greatest common divisor of $2^m+1$ and $2^n+1$ ($m,n$ are positive integers), but I don't really know. I am pretty sure that the greatest common ...
5
votes
4answers
234 views

Pairs of integer pairs with same lcm, gcd and mean

The problem is to find all pairs of two distinct pairs(up to permutation) of integer(!) numbers $(a, b)$ and $(c, d)$ s.t. $$\operatorname{lcm}(a, b) = \operatorname{lcm}(c, d)$$ $$\gcd(a, b) = \gcd(c,...
0
votes
0answers
81 views

Find the greatest $x$ that divides 14, 19, 25, 52 and leaves remainders 4, 1, 5 and 2, respectively

Given a question as follows. Find the greatest $x$ that divides 14, 19, 25, 52 and leaves remainders 4, 1, 5 and 2, respectively. For me this question does not make sense. Because the $\text{HCF}$ ...
2
votes
1answer
27 views

Number of elements of a certain order of a direct product of finite cyclic groups.

Let $G_1$ and $G_2$ be cyclic finite groups. Suppose I wanted to find the number of elements in $G_1 \times G_2$ of order k. How would I do that? I've tried using the fact that if $g_1 \in G_1$ and $...
1
vote
3answers
49 views

$\text{lcm}(|g|,|h|) = |G||H|$ implies $|g| = |G|$ and $|h| = |H|$

Let $G$ and $H$ be groups, $g \in G$, and $h \in H$. Suppose that $\text{lcm}(|g|, |h|) = |G||H|$. I want to show that $|g| = |G|$ and $|h| = |H|$. Do we use the fact that $|g| \leq |G|$ and $|h| \...
4
votes
2answers
98 views

Prove there exists $2011$ consecutive amazing integers

Recently, I have found this problem: We call a positive integer $n$ amazing if there exists positive integers $a, b, c$ such that the equality $$n = (b, c)(a, bc) + (c, a)(b, ca) + (a, b)(c, ab)$...
2
votes
1answer
74 views

GCD and LCM properties proof

The following website https://www.cut-the-knot.org/arithmetic/GcdLcmProperties.shtml presents three properties of GCD and LCM. I was trying to understand the proof of it, but the proof seems to me ...