Questions tagged [gcd-and-lcm]
Greatest common divisor 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 those questions.
1,922
questions
3
votes
5answers
206 views
Is it true that $\gcd(a+b,a+b-c)=1$ if $(a,b,c)=1$? [on hold]
Suppose $a$,$b$ and $c$ are three distinct positive integers which share no common divisor. Note that this implies that $a$, $b$, $c$ are pairwise coprime.
Is it true that $\gcd(a+b,a+b-c)=1$ ...
4
votes
4answers
153 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
79 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
26 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
47 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| \...
0
votes
0answers
19 views
Least common multiple of $a$ and $b$ is generator of greatest ideal contained in $(a) \cap (b)$
I'm a little confused by an exercise in Dummit and Foote's book "abstract algebra".
This is the exercise (ex 11 p279)
Let $R$ be a commutative ring with $1$. Prove that the least common multiple of ...
4
votes
2answers
93 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
64 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 ...
0
votes
1answer
13 views
Does $\gcd(r, \sigma(r)) = 2r - \sigma(r)$ always hold when $r$ is deficient-perfect? [duplicate]
Let $\sigma(x)$ denote the sum of divisors of the positive integer $x$. A number $r$ is called deficient-perfect if $(2r - \sigma(r)) \mid r$.
Here is my question:
Does $\gcd(r, \sigma(r)) = 2r - ...
1
vote
0answers
21 views
A gcd problem from Niven's Introduction to the theory of numbers [duplicate]
Problem:
If $(a, b) = 1$ and $p$ be an odd prime, prove that $$\left( a+b, \dfrac{a^p +b^p}{a+b} \right)=1 \quad \text{or} \quad 2$$
Source:
An Introduction to the Theory of Numbers by Ivan Niven - ...
0
votes
3answers
101 views
euclidean algorithm and linear combination for gcd
(i) Use the Euclidean Algorithm to find gcd(1253, 7930).
(ii) Using the workings in (i), find m, n ∈ Z such that
gcd(1253, 7930) = 1253m + 7930n.
i)
7930 = 1253*6 + 412
1253 = 412*3 + 17
412 = 17*...
0
votes
1answer
18 views
Graphing a function.. the definition contains min, max, gcd.
Let $x=\frac{p}{q}$, where $p,q \in \mathbb{N}$.
Graph the function;
$$f(x)=\left\{\begin{matrix}
\frac{\min(p,q)+1}{\max(p,q)+1} & \text{if }\text{GCD}(p,q)=1 \\
& \\
0 & \text{if }\...
-1
votes
2answers
36 views
If $a$ and $b$ divide $m$, then $\frac{m}{{\rm lcm}(a,b)} \,=\,\gcd\left(\frac{m}a,\frac{m}b\right)$ [duplicate]
Theorem $\ $ If $\,\ a,b\mid m\,\ $ then
$$\frac{m}{{\rm lcm}(a,b)} \,=\,\gcd\left(\frac{m}a,\frac{m}b\right)$$
Here, every variable is integer.
I tried by applying the relation between product ...
1
vote
0answers
30 views
An easy lcm property [duplicate]
Let $m=lcm(s,t)$ if $s|m', t|m'$ and $gcd(m/s, m/t)=1$, then $m=m'$, here every variable is a positive integer
I can't share my answer coz i don't know much about latex
0
votes
0answers
31 views
A property of lcm, hard to prove. [duplicate]
Prove that, If lcm(a,b)=m=ss'=tt', then gcd(s',t')=1
I tried my best, but i failed to derive the result, pls guys help me
0
votes
0answers
24 views
If $GCD(a,b)=1$, then $GCD((a+b)^m , (a-b)^m )$ is at most $2^m$? [duplicate]
I'm stuck for a few days in the following problem:
If $GCD(a,b)=1$, then $GCD((a+b)^m , (a-b)^m )$ is at most $2^m$.
Can you give me a hint?
0
votes
2answers
54 views
Problem in proof concerning division algorithm.
This is taken from the book titled: Numbers, Sequences and Series, by Keith Hirst.
I am unable to understand the logic given in Prop. 3 in sec. 2.4 as shown below (with $t$ replaced by $q$)
Let $T$ ...
0
votes
0answers
21 views
Prove that if $x$ is a multiple of $a$ and $b$, then $x$ is also a multiple of $\operatorname{lcm}(a,b)$ [duplicate]
Prove that if $x$ is a multiple of both $a$ and $b$, then $x$ is also a multiple of $\operatorname{lcm}(a,b)$.
I couldn’t write a proper conditional logic statement. Can anyone help me?
1
vote
1answer
29 views
$\gcd(p,q) = 1$, but $\gcd(p+k_1N,q)>1$
Suppose that p and q are naturals such that $\gcd(p,q) = 1$. Let $N \in \mathbb{N}$ be arbitrary and suppose that $\gcd(p+k_1N,q)>1$ for some $k_1 \in \mathbb{Z}$. Does there exist $k_2 \in \mathbb{...
0
votes
0answers
43 views
Maximum Pairwise GCD from an even subsequence of an array
I am trying to solve a particular problem, where I have been given an array of integers and an integer X and I need to obtain the maximum pairwise gcd from a subsequence of the array given that the ...
-2
votes
2answers
49 views
Find all positive integers $a$ and $b$ satisfying $\gcd (a,b)=10$ and $\operatorname{lcm} (a,b)=100$ simultaneously. [closed]
Find all positive integers $a$ and $b$ satisfying
$$\gcd (a,b)=10$$
and
$$\operatorname{lcm} (a,b)=100$$
simultaneously.
0
votes
1answer
32 views
Divisibility Question, a bit difficult(for me). [duplicate]
Taken from An Introduction to the Theory of Numbers by Niven et al:
Prove that if $m\gt n$ then $a^{2^n}+1$ is a divisor of $a^{2^m}-1$. Show that if $a,m,n$ are positive with $m\ne n$, then:
$gcd(a^...
0
votes
1answer
41 views
Let $R$ be a UFD and $a,b,c \in R$ be nonzero. If $c \mid ab$ and $\gcd(a, c) = 1$, then $c \mid b$. [duplicate]
Here is the problem
If $c\ |\ ab$ and $\text{gcd}(a,c)=1$ then $c\ |\ b$
Here's my approach. There exists $x,y$ such that $ax+cy=1$, so $c\ |\ axb+cyb=b$
I'm pretty sure my first step is wrong. Any ...
0
votes
2answers
51 views
How co prime numbers can be used to form any number beyond a number [duplicate]
Suppose we have two co prime numbers a and b. Then it is always possible to form any number greater than or equal to a*b - a - b +1 by using the given co primes only that is
ax + by
where x and y ...
1
vote
1answer
37 views
Is brute force trial the only approach to find smallest k such that (840k + 3) is a multiple of 9?
The following is the answer approach given for the below problem in my old book. I am skeptical about the brute trial approach suggested (though k is found after 2 trials in this case). Is there a ...
0
votes
2answers
33 views
Suppose two integers $a,N$, where N is prime, is there a difference between requiring $gcd(a,N)=1$ and $N \not\mid \!\!\;a $?
This is probably painfully obvious but I wanted to confirm if there's any difference between requiring that the $gcd(a,N)=1$ or $N \not\mid \!\!\;a $ if N is prime? That is, could you use either ...
1
vote
1answer
48 views
sub-resultant GCD algorithm for polynomials over a field
I'm trying to implement the algorithm for factoring polynomials over number fields on page 145 of Henri Cohen's A Course on Computational Algebraic Number Theory, but I'm not sure how the application ...
2
votes
1answer
132 views
Compute $\gcd(a+b, 2a+3b)$ if $\gcd(a,b) = 1$
A question from a problem set is asking to compute the value of $\gcd(a+b, 2a+3b)$ if $\gcd(a+b) = 1$, or if it isn't possible, prove why.
Here's how I ended up doing it:
$\gcd(a,b) = 1$ implies ...
3
votes
2answers
103 views
Proof explanation: suppose $a\mid bc$ and $\gcd(a, b) = 1$. Then $a\mid c$.
I have been given a proof, but I do not understand the "why" behind it. If someone could explain me each of its steps with great detail that would be amazing!
The proof I was given is the following ...
1
vote
1answer
48 views
What is the significance of $(n,m)=1$ in this proof that the Euler phi function is multiplicative?
In the proof reported in Aaron Grecius's notes on Euler’s Phi Function (p. 1) where is the fact that $(n,m)=1$ actually used ? I'm having trouble understanding it's significance.
0
votes
2answers
66 views
How to solve $y^3=x(x+1)$ where $x$ and $y$ are integers? [closed]
How to solve $y^3=x(x+1)$ where $x$ and $y$ are integers ?
Can you help me ?
Thanks :)
0
votes
1answer
68 views
“Factor” a number into 1-16 products and sum parts
I have a number N (integer 32 bits) that I need to "factor" into 1-16 product and sum parts. Let me explain:
For $N = 256$, I want: $(16 \times 16)$
For $N = 257$, I want: $(16 \times 16) + 1$
For $N ...
2
votes
2answers
61 views
Method for finding the coefficients in Bezout's identity without using extended euclidean algorithm [closed]
Every book I have seen uses the extended euclidean algorithm for computing the coefficients of Bezout's identity. I feel that it is very tedious and time consuming. Is there a simpler and shorter ...
-1
votes
2answers
25 views
Why are these two monic complex polynomials coprime?
Let $P(x), Q(x) \in \mathbb{C}[x]$ two monic complex polynomials. It is given that $P(x)$ divides $Q(x)^2+1$ and $Q(x)$ divides $P(x)^2+1$.
Why does it follow from these conditions that $P(x)$ and $Q(...
2
votes
1answer
137 views
Factor $x^p-y^p$
I would like to factor the polynomial $p(x,y)=x^p-y^p$ for some small prime $p$ $(p=3,5,\text{or } 7)$ and for all values of $p(x,y)$ with $1 < x < 1000$ and $1 < y < x$.
There is a ...
2
votes
1answer
51 views
prove or disprove if $ab\equiv ac \bmod m$ then $b\equiv c \bmod m$
prove or disprove
if $ab\equiv ac \bmod m$ then $b\equiv c \bmod m$
there is a theorem said that this equality holds when gcd(a,m)=1 so I try to find a counterexample to disprove this
for example
$...
1
vote
1answer
40 views
Finding $\operatorname{lcm}\big(t-1,(1-t)^2\big)$. [closed]
I get $2$ answers for this question:
$$(t-1)^2 \quad \textrm{and} \quad -(t-1)^2$$
Which one is correct ? Why ?
Is it a must for the LCM to be positive? Im confused. Please help.
0
votes
3answers
43 views
Common factor $x^4+6x^2+25$ & $3x^4+4x^2+28x+5$
If $f(x)=x^2+bx+c$ where b,c are Real number and $f(x)$ is a factor of both $x^4+6x^2+25$ & $3x^4+4x^2+28x+5$ then find the value of $f(x)$.
I manage to get the answer by dividing the function by ...
0
votes
1answer
63 views
General formula for the gcd.
It seems there is no closed form for the greatest common divisor of any two given integers.
Why is there no such formula?
Does the only way to compute the gcd is essentially to recursively apply the ...
0
votes
2answers
46 views
How to find GCD of those two complex polynomials?
I have a polynomial
$$f(x) = i(x^2-1)^3+(x^2+1)^3-8x^3$$
I want to check if this has repeated roots. To do so, I'll find greatest common divisor (euclidean algorithm) of $f(x)$ and its derivative $f'...
1
vote
0answers
29 views
GCD and LCM of powers in GCD domains
Let $R$ be a GCD domain. This means that it is an integral domain in which any 2 elements have a GCD, and hence also an LCM.
Question:
Is it true that if $z$ is a GCD or LCM of $x$ and $y$ in $R$, ...
0
votes
1answer
46 views
GCD in multivariate polynomial ring and quotient ring
1. GCD in multivariate polynomial ring
I would like to prove the following but couldn't figure out how to.
Let $d$ and $h_1, h_2, \cdots, h_k$ be multivariate ...
1
vote
1answer
72 views
How do I prove Bézout's identity of polynomials in $F[x]$?
$F$ is a field.
$a(x),b(x)\in F[X]- F$.
$\gcd(a(x),b(x)) = d(x)$ and $u(x)a(x)+v(x)b(x)=d(x)$.
I need to prove that: $\deg(u)<\deg(b)-\deg(d)$.
I use the fact that degree is replacing the absolute ...
0
votes
1answer
52 views
Proof that if $\gcd(a,b) = 1$ then $\gcd(a^n, b^m) = 1$ [duplicate]
Proof via induction for $n,m \geq 0$ that if $\gcd(a,b) = 1$ then $\gcd(a^n, b^m) = 1$ for any $n,m$ that are positive integers.
4
votes
2answers
394 views
How to calculate the GCD?
How to evaluate the following with the help of Mobius function ?
$$\displaystyle\sum_{i=1}^n \sum_{j=i+1}^n \sum_{k=j+1}^n \sum_{l=k+1}^n {gcd(i,j,k,l)^4} .$$
In other words, we have to ...
