Questions tagged [gcd-and-lcm]

Use for questions related to gcd (greatest common divisor), lcm (least common multiple), and related concepts from integer and ring theory.

Filter by
Sorted by
Tagged with
-5
votes
0answers
17 views

Let a, b ∈ Z, not both zero. Prove gcd(−a, b) = gcd(a,−b). [closed]

Let a,b ∈ Z, not both zero. Prove gcd(−a, b) = gcd(a,−b).
2
votes
2answers
71 views

Halving input but not at each step of a process

I am reading about an algorithm that takes as input $2$ integers and does the following to calculate the GCD: If both are even then then shift right (=division by $2$) both numbers and repeat If one ...
0
votes
3answers
57 views

determine the gcd of $n^3+3n^2-5 $ and $ n+2$ [duplicate]

Hello I have to determine the gcd of $n^3+3n^2-5 $ and $ n+2$, but I can’t do it because I know we have to eliminate the $n$. I tried to eliminate $n^3 $ but I’m stuck for the rest.
-4
votes
0answers
15 views

Question from Least Common Factor [closed]

What is the Least common factor (LCM) -2 and 2?
0
votes
1answer
26 views

Show that $\gcd(5a+8, 7a+3)=1\textrm{ or } 41$. Best way to solve a problem of this sort? [duplicate]

Let $a\in \mathbb Z$. Show that $\gcd(5a+8, 7a+3)=1\textrm{ or } 41$. Knowing that $\forall k \in\mathbb Z, \gcd(a,b)=\gcd(b, a-kb)$. I actually know how to solve this particular problem: $\gcd(5a+8, ...
-1
votes
2answers
49 views

Sum of GCD and LCM is the sum of those numbers [closed]

I'm really stuck with this. Let $a,b\in \mathbb{Z}^+$ such that $$ GCD(a,b) + LCM(a,b) = a+b $$ then either $a|b$ or $b|a$. I tried using the fact that the GCD is a linear combination of the numbers ...
1
vote
1answer
45 views

Let $a,b\in\mathbb Z$ such that $\gcd(a,b)=5$. Find $\gcd(25ab^2, a^4 + b^4)$.

Let $a,b\in\mathbb Z$ such that $\gcd(a,b)=5$. Find $\gcd(25ab^2, a^4+b^4)=d$. This is all I managed to think of: $a=5k_1$ and $b=5k_2$. Therefore, $25ab^2=3125k_1k_2^2$ and $a^4+b^4=625(k_1^4+k_2^4)$...
0
votes
0answers
13 views

Let a, b ∈ Z+ such that a, b > 1. Use proof by contrapositive to prove: If gcd(a, b) = 1, then for all primes p, p∤a or p∤b. [duplicate]

I am having trouble getting this question completely correct. Can anyone help with the answer?
0
votes
2answers
75 views

Show $t^5-5t+1$ has no multiplicities [duplicate]

Problem Show that $f(t)=t^5-5t+1$ has no repeated roots. My initial idea I write $f$ in terms of linear factors $(t-\alpha_1)...(t-\alpha_5)$ where all the $\alpha_i$ make up the five roots of $f$. I’...
-1
votes
0answers
29 views

What is the result of GCD(A+X,B+X) and why?

I found a question on the result of $\gcd(ax,bx)$. But I wonder if there is any formula or proof for computing $\gcd(a+x,b+x)$! Can You help me?
1
vote
2answers
50 views

Dividing two numbers by their GCD to obtain relative primes [duplicate]

If we divide $15$ and $81$ by $(15, 81) = 3$, we obtain two relatively prime integers, $5$ and $27$. This is no surprise because we have removed all common factors. This illustrates the following ...
-1
votes
1answer
42 views

Find the least number of muffins baked [closed]

This question appeared in Aryabhatta Inter School Maths Competition 2020 Tejaswini is baking muffins. When she packs 3 muffins in a box, 2 muffins are left. If she packs 5 muffins in a box, 3 muffins ...
0
votes
0answers
26 views

How to quickly identify common factors [duplicate]

What's a good approach for identifying potentially large common factors? For example, how do I quickly recognise that 123543/99900 is reducible to 371/300? Or putting this another way, how do I ...
-1
votes
0answers
22 views

A problem about greatest common divisor [duplicate]

Let $a$, $b$ and $c$ be integers and $\gcd(a,b)=1$. Show that there exists an integer $n$ such that $\gcd(an+b,c)=1$.
-3
votes
1answer
53 views

Find $\gcd\{(a^{2^n} + 1),(a^{2^m}+1)\}\;$ where $\;m\;$ and $\;n\;$ are positive distinct integer primes. [duplicate]

Let $a>1$ be an integer. Find $\gcd\left((a^{2^n} + 1),(a^{2^m}+1)\right)\;$ where $m$ and $n$ are both positive distinct integer primes.
1
vote
1answer
36 views

How to test if a polynomial GCD is correct

I'm studying the Zippel algorithm for computing multivariate polynomial GCDs, which is probabilistic in the sense that it uses some random numbers, and assumes that if a polynomial coefficient is zero,...
0
votes
0answers
32 views

From $g(n)$ to $l(n)$ [closed]

Is it possible to switch from a sum of gcd to a sum of lcm ? I explain, if i have : $g(n) = \sum_{i=1}^{n} gcd(i, n)$ Can I get the sum $l(n)$ where : $l(n) = \sum_{i=1}^{n} lcm(i, n)$ ? I have not ...
2
votes
0answers
42 views

Is this a valid proof for $\gcd(a,b) = \gcd(b,r),\ r = a-bq$? [duplicate]

Let $ a \in \mathbb{N}$, $ b \in \mathbb{N}_0 $, $ r \in \mathbb{N}_0 $, $ q\in \mathbb{N} $ and $ b \leq a$ so that $$a = bq + r $$with $$ 0 \leq r \lt b$$ Proof: Let $ D = \{d \in \mathbb{Z} \vert ~...
-1
votes
0answers
26 views

Finding GCD of two numbers [duplicate]

Let (a,b) denote the gcd of the numbers a and b. Let $X=((61^{610}+1,61^{671}-1)^{671}+1,(61^{610}+1,61^{671}-1)^{610}-1)$ a) Find $X$mod $10$ b) What is the minimum number of bits required to ...
2
votes
1answer
55 views

Let $M$ be a commutative monoid with the cancelation law. Show that an lcm doesn´t exist under these conditions.

Let $M$ be a commutative monoid with the cancelation law and suppose that $a \nsim b, x \nsim y, ax = by, ay = bx$, and $a$ and $b$ are irreducible. A first question was to show that $\gcd(ax,bx) = \...
-1
votes
1answer
52 views

A question related to GCD of polynomials

Consider the non-zero polynomials $P(t)=at+b$ and $Q(t)=ct+d$ in $F[t]$ such that at least one of them is non-constant. Then, $(P(t),Q(t))=1$ if and only if $ad-bc\neq0$. I'm stuck on this problem and ...
0
votes
2answers
31 views

Simple question about GCD [duplicate]

Let $a,b,c,d \in \mathbb{Z}$. If $\gcd(ac,bd)=1$, then $\gcd(a,b)=\gcd(c,d)=1$? Couldn't find any counterexample for that affirmation, all I can find is examples of it working. Like we having: $$\gcd(...
1
vote
1answer
69 views

Prove that the sum of reciprocals of product of relatively primes less than $n$ is $1$ [closed]

$n \geq 2$ is an integer. $B$ is a set which contains all ordered couples of natural numbers $(a,b)$ with following properties: $a,b \leqslant n$ , $\gcd(a,b)=1$ , and $ a + b > n $. Show that : $$\...
2
votes
0answers
23 views

In my final answers regarding pressure vessel design problem can't satisfy the constraints , which needs to be muliple of 0.0625

I need to solve a pressure vessel design problem. The objective is to minimize the total cost, including the cost of material, forming and welding. The solution has four values ...
0
votes
1answer
32 views

Number of $1\leq n \leq 1000$ such that $\gcd(n,3000)=5$

How can I determine the number of $1\leq n \leq 1000$ with $n \in \mathbb N$ such that $\gcd(n,3000)=5$? 'gcd' stands for greatest common divisor. What would be a good way to solve this problem? I ...
-1
votes
1answer
43 views

GCD (a,b) =1 prove GCD ( (a+b), (a-b) ) = 1 or 2 [duplicate]

if GCD of $(a, b) = 1$, prove that GCD $(a+b, a-b) = 1$ or $2 .$ The proof goes like: Let GCD $( a+b, a-b ) = d$ and let there exist integers m and n such that $ a+b =md$ and $ a-b = nd.$ By adding ...
1
vote
1answer
36 views

Showing $\gcd(a,b,c) = \gcd(a,\gcd(b,c))$ without using Bezout's lemma and only the definition of the gcd [duplicate]

Let $a,b,c \in \mathbb{Z}$ where $(b,c) \neq (0,0)$. I would like to show that $$ \gcd(a,b,c) = \gcd(a,\gcd(b,c)). $$ The definition of the greatest common divisor (gcd) we received in our class is $$...
1
vote
1answer
36 views

Polynomial division - Bézout's theorem [duplicate]

Consider the equation $(x^3-3x^2+4x-2)s(x)+(x^2-1)t(x)=x+1$. How can we find polynomials $s(x), t(x)$ which satisfy this equation? Clearly $x+1$ divides the term involving $t(x)$ but not the first ...
1
vote
2answers
27 views

Does lcm of multiple numbers also divide any common multiple of these numbers? [duplicate]

I know that this is true for two numbers, but does this also hold for more than two? I.e. if $m$ is a common multiple of several numbers $n_1, \ldots , n_k$, does it hold that lcm$(n_1,\ldots,n_k)$ ...
0
votes
0answers
48 views

Finitely generated submonoids of commutative cancellative gcd monoids

Let $(M,\cdot,1)$ be a commutative cancellative gcd monoid. That is, $\forall a,b\in M\colon a\cdot b =b\cdot a$ $\forall a,b,c\in M\colon (c\cdot a = c\cdot b)\implies (a=b)$ $\forall a,b\in M\colon ...
1
vote
1answer
82 views

Sum of two numbers $x, y = 1050$. What is the maximum value of the HCF between $x$ and $y$?

Let $HCF (x, y) = h$ then we can say that $x=ha$ and $y=hb$ for some multiple of $h$ i.e. $a$ and $b$ respectively and where $ HCF(a,b)=1$ . As per question :- $x+y = 1050$ $\Rightarrow ha+hb = 1050$ ...
2
votes
2answers
56 views

How many pairs of positive integers $x, y$ exist such that $HCF (x, y) + LCM (x, y) = 91?$

Let $HCF (x, y) = h$ then we can say that $x=ha$ and $y=hb$ for some multiple of $h$ i.e. $a$ and $b$ respectively. Let $LCM(x, y) = k$ We know that :- $HCF (x, y) \times LCM(x, y) = x \times y$ $\...
2
votes
2answers
55 views

There are 3 numbers $a,b,c$ such that $HCF(a,b)=l,HCF(b,c)=m$ and $HCF(c,a)=n$. $HCF(l,m)=HCF(l,n)=HCF(n,m)=1$. Find LCM of $a, b, c$.

My solution approach for this problem was to use the relationship formula between LCM and HCF of three numbers which is $$LCM(p,q,r)=\frac{pqr \times HCF(p,q,r)}{HCF(p,q) \times HCF(q,r) \times HCF(r,...
0
votes
1answer
72 views

Proving that gcd$(2^{2k-1}-3^k,4^k - 3^k)=1$ [duplicate]

Let: gcd$(a,b)$ be the greatest common divisor of $a$ and $b$ $f = $gcd$(2^{2k-1}-3^k, 4^k - 3^k)$ It seems to me that $f=1$. I am not clear how to prove this. Would this be a valid argument: (1) $...
0
votes
0answers
55 views

Given a map $f : \mathbb{Q} \to \mathbb{Z}\times \mathbb{N},$ prove that $f$ is injective.

The full question: Define a map $f : \mathbb{Q} \to \mathbb{Z}\times \mathbb{N}$ by $f(x) = (z, n)$ if $x = \frac{z}{n} \in \mathbb{Q}$ with $z \in \mathbb{Z}$ and $n \in \mathbb{N}$ and $\gcd(z,n) = ...
1
vote
0answers
57 views

Equality for GCD and LCM of integers

[Update: I see that the equality is wrong: Assume that p divide the right hand side. If p|(c,e) and p|(d,e), then p need not to divide the left hand side. Thank you all for your comments] Let $a,b,c,d,...
0
votes
3answers
81 views

$\gcd(3n^2+1, 2n-3)$

I want to show that $\gcd(3n^2+1, 2n-3)$ divides 31 $\forall n\in\mathbb{N}$. I have tried to begin by eliminating the $3n^2$ factor on the left by adding and subtracting multiples and powers of $2n-3$...
0
votes
0answers
113 views

Gcd of two numbers of the form $x^a-x^b$

Inspired by this question, which noted that for all natural numbers $a>2$, $(2^{15}-2^3)|(a^{15}-a^3)$. My question deals with generalizing this: Let let $a,b$ be integers such that $a>b\geq1$. ...
1
vote
1answer
46 views

Irreducible polynomial written as $ap + bq$ [duplicate]

I want to know if the following proposition is true or false : Let $p$ and $q$ $\in \mathbb Q[X]$ two polynomials of degree $\geq 1$ and let $g$ $\in \mathbb Q[X]$ an irreducible unitary polynomial, ...
1
vote
3answers
50 views

$a_1<a_2<a_3<a_4$ such that $\sum_{i=1}^4\frac{1}{a_i}=\frac{11}{6}$

Give that $a_1<a_2<a_3<a_4$ are positive integers such that $$\sum_{i=1}^4\frac{1}{a_i}=\frac{11}{6}$$, find the value of $a_4-a_2$. My try: Since $11$ is prime, atleast one of $a_1,a_2,a_3,...
-2
votes
4answers
72 views

Prove that $\gcd(5x+2y,2x+y)=1$ if $\gcd(x,y)=1$ [duplicate]

Let $\gcd(x,y)=1$. Prove that $5x+2y$ and $2y+x$ are always co-prime. I’ve tried a lot of things (really a lot), but nothing has worked for me. One of the best ideas that came to my mind (I think) is ...
0
votes
3answers
132 views

How to find $\gcd(n+1, n^2+7)$?

I've tried to use the rule that if $ b>a$, then $\gcd(a,b)=\gcd(b,b−a)$, as well as the properties of divisibility by adding and subtracting the terms from each other but haven't been able to reach ...
1
vote
2answers
78 views

GCD Proof of Odd Numbers [duplicate]

I found this problem in Discrete Mathematics and Its Applications while studying for an exam and am having trouble solving it. Prove that for $a,b\in N^*, a \ge b, 2\gcd(a,b) = \gcd(a+b, a-b)$ if $a$ ...
0
votes
1answer
23 views

How can I prove that for modular multiplicative inverses that if $∃ $[$b$]$ ∈ℤ_n$ such that [$a$] * [$b$] = [$1$], then gcd($a,n$) =$1$? [duplicate]

How can I prove that for modular multiplicative inverses that if $∃ $[$b$]$ ∈ℤ_n$ such that [$a$] * [$b$] = [$1$], then gcd($a,n$) =$1$? I understand the relationship between primes and multiplicative ...
0
votes
2answers
60 views

Formulas for lcm of three integers [closed]

I know that both of the following formulas equal to $\text{lcm}(a,b,c)$, but how can we show that $\dfrac{abc \cdot \gcd(a,b,c)}{\gcd(a,b) \cdot \gcd(a,c) \cdot \gcd(b,c)} = \dfrac{abc }{\gcd(ab,ac,...
-1
votes
4answers
41 views

Find the GCD of a polynomial using the extended Euclidean algorithm and express it in the form $a(x)f(x)+b(x)g(x)$ [duplicate]

I am working on a problem that I can not seem to finish. Find the gcd of $f(x)=x^7+1$ and $g(x)=x^6+x^5+x^3+1$, and express it in the form $a(x)f(x)+b(x)g(x)$ using the extended euclidean algorithm. I ...
1
vote
4answers
56 views

Find numbers from GCD and LCM [duplicate]

two numbers gcd and lcm are respectively 6 and 600. What is the possible pairs of two numbers?
0
votes
0answers
17 views

Prove that $\gcd(a^{2^m}+1,a^{2^n}+1)=\begin{cases} 1,& \text{ if } a\ \text{is even;} \\ 2 & \text{ if } a\ \text{is odd.} \end{cases}$. [duplicate]

Show that if m> n, then $a^{2^n} + 1$ is a divisor of $a^{2^m} -1$. Show that if $ a, m, n \in \mathbb Z ^ + $ with $ m \neq n $, then $$\gcd(a^{2^m}+1,a^{2^n}+1)=\begin{cases} 1,& \text{ if } ...
0
votes
0answers
49 views

Need help understanding this tricky LCM problem. [duplicate]

[Moderators please note this is NOT a duplicate of GRE problem involving LCD, prime factorization, and sets. LCM. What am I missing? GRE test prep question [LCM and divisors] These posts only answer ...

1
2 3 4 5
52