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
-1
votes
3answers
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$?
0
votes
2answers
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.
0
votes
0answers
10 views

Count number of valid sequences that satisfy pairwise LCM

Suppose there is a sequence of $n$ positive integer numbers, e.g., for $n = 3, A_1, A_2, A_3$. We are given pairwise LCM (prime factorization of LCM, to be specific) of some pairs of them, e.g., $LCM(...
1
vote
1answer
30 views

LCM: Counting number of digits

If the least common multiple of two 6-digit integers has 10 digits, then their greatest common divisor has at most how many digits? I can not figure out a way to solve this. I thought that the answer ...
0
votes
0answers
32 views

Number of sequences of given type. [closed]

Consider that there is sequence $a$ of length $n$ ,$a=[a_i,0\le i\le n]$. Now you are given with $\text{lcm}$ of some pairs of number from list that is, $\operatorname{lcm}(a_i,a_j)=k$ for $0\le i,j\...
1
vote
1answer
22 views

Determination of the value of $n$ in $\mathbb{Z}_n$ subject to $x+y=2$ and $2x-3y=3$

$\mathbf{Question}$: Determine the integers $n$ for which $\mathbb{Z}_n$, the set of integers modulo $n$, contains elements $x,y$ so that $x+y=2$, $2x-3y=3$. $\mathbf{Attempt}$: Let us put $x=n\alpha+...
-1
votes
0answers
30 views

Conclude that $g|n_1$ and $g|n_2$, and so $g \leq \text{gcd}(n_1, n_2)$. [closed]

Let $n_1$ and $n_2$ be natural numbers. Then $\text{gcd}(n_1,n_2)$ is the smallest natural number in the set $A = \{n_1m_1 + n_2m_2|m_1,m_2\in\mathbb Z\}$.
2
votes
2answers
86 views

If $ \gcd(a,b) = 1$ prove that $ \gcd(2a+b, a+2b) = 1$ or $3$?

I have seen this question, some other related questions and answers for solving this problem. However, I tried to solve it using a different approach. Let, $ \gcd(2a+b, a+2b) = d$ Assume $2a+b = qd\...
0
votes
0answers
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 ...
2
votes
1answer
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$ ...
1
vote
0answers
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 ...
2
votes
2answers
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 ...
2
votes
1answer
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$ ...
0
votes
1answer
35 views

How to calculate the number of integer pairs whose LCM is x?

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)...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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)$
1
vote
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 ...
1
vote
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 ...
2
votes
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 = ...
2
votes
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+...
-6
votes
3answers
37 views

Solve the Diophantine equation [closed]

They ask me to solve: $98x+34y=2$ Please I need help.
2
votes
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 ...
4
votes
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 ...
3
votes
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 ...
0
votes
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 ...
0
votes
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, ...
1
vote
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 ...
1
vote
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{...
1
vote
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
0
votes
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 ...
0
votes
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 ...
5
votes
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 ...
0
votes
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!
3
votes
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 ...
3
votes
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?
1
vote
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 ...
1
vote
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+...
0
votes
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.
1
vote
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, ...
-1
votes
2answers
36 views

Since the gcd of two numbers is not unique, shouldn't “gcd” be read “great common divisor” instead of “greatest common divisor”?

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

Bezout's coefficients proof

I have a little problem with proof one property of Bezout's coefficients. Given $a,b$, there are exactly two pairs of integers $x,y$ such that: $xa+yb = gcd(a,b)$ and $|x| \leq \frac{b}{gcd(a,b)}, |y| ...
0
votes
0answers
27 views

Let a and b be two positive integers with $d = \gcd(a,b)$. Show that $\gcd\left(2^a-1,2^b-1\right) = 2^d-1$. [duplicate]

Let a and b be two positive integers with $d = \gcd(a,b)$. Show that $\gcd\left(2^a-1,2^b-1\right) = 2^d-1$.
-3
votes
1answer
38 views

Prove that if $gcd(a, b)=d$ then $gcd(a^2, b^2 )=d^2$ [duplicate]

how can i prove that? Prove that if $gcd(a, b)=d$, then $gcd(a^2, b^2 )=d^2$
0
votes
1answer
76 views

When does $a\mid c$ and $b\mid c$ imply $ab\mid c$? [duplicate]

For example, $$2\mid12,3\mid12,6\mid12$$ But, $$4\mid12,6\mid12,24 \nmid 12$$ When does it work?
0
votes
2answers
17 views

GCD of Gaussian Integers $\text{gcd}(4, 36+18i)$

I have to compute $\text{gcd}(4, 36+18i)$. I computed the norms: $16$ and $1620$. I am sure $2$ is the gcd. Is there any method to prove $2$ is the gcd, other than using the Euclidean Algorithm (...
0
votes
2answers
5 views

How to prove that total numbers which are divisible by $a$ and $b$ and are less than $N$ are always $\lfloor N/LCM(a,b) \rfloor$?

I am trying to solve this question : find total numbers which are divisible by $a$ and $b$ and are less than $N$ are always $\lfloor N/LCM(a,b) \rfloor$, by intuition I first find all numbers which ...
0
votes
1answer
23 views

Algebra(Euclid method)

I couldn’t solve this question and I don’t know how to figure this out from beginning. Hint from my school was to think about euclid method on $ α^m-1,α^n-1$,and better to think $α$ as Polynomial. ...
1
vote
1answer
42 views

Basic Number Theory Question involving quadratic equations and squares

Question : Let $m,n\in \mathbb{N}$ such that $2m^2 + m = 2n^2 + n$, then prove that $m - n$ and $2m + 2n + 1$ are perfect squares. $\begin{align}2m^2-2n^2 &=n-m\\ -2(n-m)(m+n) &= n-m \\\end{...

1
2 3 4 5
46