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

2,267 questions
Filter by
Sorted by
Tagged with
49 views

### If $a-b \mid ax-by$, then $\gcd(x,y) \ne1$? [closed]

So is this true for positive integers $a,b,x,y>1$ with $a>b$ and $x>y$?
21 views

### How to find 2 numbers with given sum and minimum LCM?

How to find 2 numbers with given sum and minimum LCM? for example if sum = 9 then two numbers are 3 and 6 since 3 + 6 = 9 and LCM(3, 6) = miniminum possible.
10 views

22 views

25 views

### Is there a property relating gcd(a, b) % c and gcd(a %c, b%c) % c. Here all a,b,c are natural numbers i.e.>0 and '%' represents modulo operator.

I have been facing some difficulty solving problems relating the gcd and modulo operator. If I use the Euclidean algorithm then it works fine when either a or b is small because in one step itself a ...
67 views

### Find smallest $x$ such that $\gcd(a + x, b + x) = c$.

I need to find the smallest $x$ such that $$\gcd(a + x, b + x) = c$$ where $a, b, c, x$ are positive integers and $a \le b$. I was able to rewrite it as $$\gcd(a + x, b - a) = c$$ This shows that $c$ ...
38 views

### GCD of Ideal: How we get $\gcd(I, J) = I + J$?

Take any two non-zero ideals $I$ and $J$ in $R$. Since we know that ideals in a Dedekind domain factors uniquely into prime ideals $$I = \prod_i P_i^{m_i}, J = \prod_i P_i^{n_i}$$ where $P_i$’s are ...
66 views

### A question regarding the proof of $\gcd(a^m-1, a^n-1) = a^{\gcd(m,n)}-1$

I have a problem trying to understand the proof: Theorem $\boldsymbol{1.1.5.}$ For natural numbers $a,m,n$, $\gcd\left(a^m-1,a^n-1\right)=a^{\gcd(m,n)}-1$ Outline. Note that by the Euclidean ...
31 views

### Proof verification of a number theory problem involving sequences.

$\textbf{Question:}$Does there exist an infinite sequence of integers $a_1, a_2, . . .$ such that $gcd(a_m, a_n) = 1$ if and only if $|m - n| = 1$? $\textbf{My solution:}$Suppose we have a $n$ ...
35 views

It is given that $x$ can be represented as power of at-most 5 primes. Example, x = $2^2.3^1.5^1.7^1.11^1$ = $4620$ Another example :- $x=2^2$ Possible integer pairs with LCM = 4 : $1)(2^2,2^0)$ $2)... 2answers 32 views ### Let$a,b \in \mathbb{Z}$and let$d = gcd(a,b)$. Show that$\{ ka + lb: k,l \in \mathbb{Z}\} = \{md : m \in \mathbb{Z} \}$I know that given$d = gcd(a,b)$that this also means$xa + yb = d$. Using this we get (showing from left to right side) $$xa + yb = d$$ $$m(xa + yb) = md$$ $$xma + ymb = md$$ Now I am unsure how to ... 2answers 40 views ### Given that$a,b \in \mathbb{Z}$and are nonzero. Why is it that$\frac{a}{\gcd(a,b)}$and$\frac{b}{\gcd(a,b)}$are coprime? [duplicate] I understand the definition of coprime, which is$\gcd(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}) = 1$or$x(\frac{a}{\gcd(a,b)}) + y(\frac{b}{\gcd(a,b)}) = 1$. I am pretty sure that I have to use the ... 0answers 11 views ### Checking that U(n) is a set that is closed under multiplication modulo n [duplicate] In Joseph Gallian's Contemporary Abstract Algebra, example 11 of chapter 2, the author leaves it to the reader to check closure for U(n), so I am trying to figure out if my solution is correct, or ... 2answers 28 views ### Prove$\gcd (2^n- 1 ;2^m-1) = (2^d-1)$[duplicate] Looking for a high school level proof of$\gcd (2^n-1 ; 2^m-1)=(2^d-1)$Where$d= \gcd(m;n)$1answer 41 views ### Prove that the set of all positive integers less than$n$and relatively prime to n form a group under multiplication modulo n I came across the problem Prove that the set of all positive integers less than$n$and relatively prime to n form a group under multiplication modulo n. Proving the associativity of multiplication ... 1answer 40 views ### Is it true that$HCF(HCF(a,b),c)=HCF(a,HCF(b,c))$If$a,b,c$are any three positive integers, Is it true that$HCF(HCF(a,b),c)=HCF(a,HCF(b,c))$My try: Case$1.$if atleast one of$a,b,c$is equal to ONE , then the claim is True. case$2.$If every ... 0answers 50 views ### If$N = q^k n^2$is an odd perfect number with special prime$q$, then can$N$be of the form$q^k \cdot (\sigma(q^k)/2) \cdot {n}$? Let$\sigma(x)$denote the sum of divisors of the positive integer$x$. A number$M$is said to be perfect if$\sigma(M)=2M$. For example,$6$and$28$are perfect since $$\sigma(6) = 1 + 2 + 3 + 6 = ... 2answers 74 views ### Is the statement “(m, n)=d if and only if there exist integers r and s such that r m+s n=d” problematic? My textbook Groups, Matrices, and Vector Spaces - A Group Theoretic Approach to Linear Algebra by James B. Carrell said that (m, n)=d if and only if there exist integers r and s such that r m+... 3answers 37 views ### Solve the Diophantine equation [closed] They ask me to solve: 98x+34y=2 Please I need help. 1answer 32 views ### Computational complexity of a modified Euclidean algorithm The Euclidean algorithm computes the \gcd of two integers with the recursive formula$$\gcd(a,b)=\gcd(b,a\bmod b)$$and takes at worst \log_\varphi(\min(a,b)) steps, where \varphi is the golden ... 1answer 75 views ### If \operatorname{lcm}(m, m + k) = \operatorname{lcm}(n, n + k), then m = n Let m, \ n, \ k \in \Bbb N be such that \operatorname{lcm}[m , m + k] = \operatorname{lcm}[n , n + k], then prove that m = n. Though I wasn't able to proceed much, but here is a sketch of ... 2answers 64 views ### How would one use Bézout's theorem to prove that if d = \gcd(a,b)\ \text{then} \ \gcd(\dfrac{a}{d}, \dfrac{b}{d}) = 1. Note: I have checked the questions with the same title and I am after something more specific. I am doing my first course in discrete mathematics, and came across the following proposition that I was ... 1answer 37 views ### Prove that \gcd(a,b,c) = \gcd(\gcd(a,b), c), where a, b, c are all integers such that a, b are not both 0. [duplicate] I have proven until the step: x = \gcd(a,b,c) \mid \gcd(\gcd(a,b), c) = y and y \mid x, but it does not only imply that x = y, it could also imply that x = -y. How do you eliminate the case ... 2answers 35 views ### Generate the worst case 256-bit input for GCD Is there a fast method for generating the worst case 256-bit input for GCD? According to this Wikipedia article, the worst case for GCD is when the inputs are consecutive Fibonacci numbers. However, ... 2answers 20 views ### Given a,b,c,d integers, if gcd(a,b)=gcd(c,d)=gcd(b,d)=1 then show that gcd(ad+bc,bd) = 1 This question is from "Computer Algebra and Symbolic Computations", on Chapter 2, Part 2, Exe 2, (a). So far I have proved that gcd(ad,b) = 1 and that gcd(bc,d) = 1, however I am having ... 1answer 24 views ### Rouché's theorem, and distinct zeroes. I'm working on the following problem concerning Rouché's theorem: Let n\geq2. Show that the polynomial f(z)=z^n+z+1=0 has n distinct complex roots in D_2=\{z\in\mathbb{C}\hspace{0.1cm}|\hspace{... 2answers 61 views ### Proving that k|(n^k-n) for prime k Prove that for any integer n,we have (n^k)- n is divisible by k for k=3,5,7,11,13 I tried using prime factorization but that does not work here 0answers 20 views ### T-Annihilators divided by gcd divide another T-Annihilator I have a problem proving the following statement: "Let V be a K Vector-space with finite dimension, let T \in \text{End}_K(V), define p,q,h \in K[X] (K[X] is the polynomial ring with ... 2answers 38 views ### elementary number theory gcd lcm [duplicate] if m,n,k are any three positive integers prove that$$(m,n)(m,k)(n,k)[m,n,k]^2=[m,n][m,k][n,k](m,n,k)^2$$where (a,b) denotes gcd of a and b, [a,b] denotes lcm of a and b. I tried with ... 1answer 123 views ### When is the product of two “primitive” complex integers also “primitive”? I define a complex integer z = a + b\cdot i (with a, b \in \mathbb{Z}) to be primitive if gcd(a, b) = 1 and a and b have opposite parity (i.e., one is odd and the other is even). [These are ... 1answer 51 views ### How do you express “Every pair of integer has a greatest common divisor” in mathematical terms? How do you express "All pairs of integer have a greatest common divisor" in mathematical term? This is what I came up with but I'm unsure if it's right. Any help is appreciated, thanks! 2answers 57 views ### Integer solutions to m+n=\text{gcd}(m,n)+\text{lcm}(m,n)=9! Recently, I have found this problem: Given two natural numbers m and n, find the number of tuples (m,n) such that:$$m+n=\text{gcd}(m,n)+\text{lcm}(m,n)=9!$$I hav completely no idea of how to ... 2answers 111 views ### Number Theory- GCD( p!,(p-3)! -1) If p is a prime greater then 3. Then find$$ \gcd(p!,(p-3)!-1) $$gcd is probably equal to 1. But how can I show that. I think Wilson's theorem but it doesn't help me. What should I do? 4answers 96 views ### When \gcd(a,b,c)\cdot \text{lcm}(a,b,c)=\sqrt{abc} Recently, I have found this problem: Given three integer numbers a,b,c such that 1\leq a,b,c\leq 30 and the following relation holds:$$\gcd(a,b,c)\cdot \text{lcm}(a,b,c)=\sqrt{abc}$$How many ... 0answers 41 views ### Find the GCD of 2^{60}-1 and 2^{50}-1 [duplicate] My teacher said we can solve this using Euclid's division lemma but I have no clue how. I factored the numbers into$$2^{60}-1 = (2^{10}-1)(1+2^{10}+2^{20}+...+2^{50})$$and$$2^{50}-1 = (2^{10}-1)(1+... 1answer 31 views ### Reference for GCD domains I'm looking for some good references (book or document) about GCD domains and properties of them. I've googled but I have not find any. Suggestions will be appreciated. 2answers 51 views ### Largest number of different values in$f(0),f(1),..,f(999)$given$f(x)=f(398-x)=f(2158-x)=f(3214-x)$I am having trouble trying to understand the Solution (question is also linked here). The solution states that$GCD(1056, 1760) = 352$implies that$f(x)=f(352+x)$. However we also know that$GCD(398, ...
I take it that a gcd of $a$ and $b$ is, by definition, a common divisor of $a$ and $b$, and a multiple of every common divisor of those two elements. And, if I am not mistaken, more than one element ...