Questions tagged [gcd-and-lcm]
For questions related to gcd (greatest common divisor, also known as the hcf, the highest common factor), lcm (least common multiple), and related concepts from integer and ring theory.
2,605
questions
0
votes
1
answer
33
views
How to solve this problem by making a table where vertically you have the multiples of 3, horizontally, you have the multiples of 4 and five, eliminat
How to solve this problem by making a table where vertically you have the multiples of $3$, horizontally, you have the multiples of $4$ and five, then you cross out any sum of the $3m+4n$ or $3m+5k$ ...
- 11
0
votes
0
answers
41
views
How do I find a second pair of integers x and y for 200x + 85y = gcd(200,85)? [duplicate]
I understand to use the Euclidean algorithm to find gcd(200,85) and then reverse Euclidean algorithm to find a pair of integers that satisfies gcd(200,85)=200x+85y. My first pair was 200(3) + -7(85)
- 11
0
votes
0
answers
36
views
proof: if $a=bq+r$, then GCD ($a,b$) $=$ GCD($b,r$). [duplicate]
Theorem:
If $a$ and $b$ are any integers not both zero, and if $q$ and $r$ are any integers such that $a = bq + r$, then GCD($a, b$) $=$ GCD($b, r$).
Proof:
Suppose $a$ and $b$ are integers, with $...
- 93
1
vote
2
answers
82
views
Find the greatest common divisor of $ \frac {12\gcd(a,b)}{d}$ and $\frac cd $ [duplicate]
Given that the greatest common divisor of $a$, $b$ and $c$ is $d$. And 3 doesn't divide $\frac cd$, $\frac cd$ is an even integer, $\frac {c}{2d}$ is an odd integer. Find the greatest common divisor ...
1
vote
0
answers
41
views
Do all of these partial sums of roots of unity have real part = $\frac{1}{2}$ except at powers of $2$?
Let the Dirichlet inverse of the Euler totient function be:
$$\vartheta(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$
and compute the sum:
$$q(x,n)=\sum _{h=0}^{\infty } \left(\sum _{k=1}^n x^{h n+k}...
- 7,286
1
vote
0
answers
56
views
Show that $a(\gcd (n,k))$ is generated from roots of generating function of $\sum _{h=0}^{\infty } \left(\sum _{k=1}^n x^{h n+k} a(\gcd (n,k))\right)$
Let $a(n)$ be the Dirichlet inverse of the Euler totient function:
$$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$
And let the matrix $T$ be:
$$T(n,k)=a(\gcd(n,k)) \tag{2}$$
Compute the ordinary ...
- 7,286
0
votes
0
answers
50
views
Proof: Suppose $a,b \in \mathbb{N}$. Then a = gcd(a,b) iff $a|b$. [duplicate]
So I've constructed a proof for this answer and I'm having trouble completeing it. To prove iff statements we need to prove the statment $P \rightarrow Q$ then $Q \rightarrow P$. Convert the statement ...
- 147
0
votes
1
answer
29
views
System of equations involving lcm [duplicate]
Given a system:
$$
\begin{cases}
5x - 3y = 0 \\
\text{lcm}(x, y) = 45
\end{cases}
$$
Since, $5x=3y$, I've tried expressing product of $xy$ as:
$$
\text{lcm}(x,y)\gcd(x,y)=xy \\
\gcd(x,y)=\frac{xy}{\...
- 3
-2
votes
2
answers
71
views
Prove ${\gcd\left({\rm lcm}\left(m_1,m_2\right),m_3\right){\rm lcm}\left(m_1,m_2,m_3\right)} = {\rm lcm}(m_1,m_2)m_3$ [duplicate]
Is it possible to proof: when $gcd\left(m_1,m_2,m_3\right)=1$, then $\frac{lcm\left(m_1,m_2\right)m_3}{gcd\left(lcm\left(m_1,m_2\right),m_3\right)}=\frac{lcm\left(m_1,m_2,m_3\right)}{gcd\left(m_1,m_2,...
- 107
-2
votes
0
answers
35
views
Calculate GCD of polynomial [duplicate]
I have tried so hard to solve this but I always ended up with $\frac{2}{9}$ but it is 1 GCD $x^5+x+1$, $x^3+2x^2+1$
0
votes
0
answers
61
views
LCM and GCD of numbers with euclidean algorithm.
I know that given two numbers $a$ and $b$ such that $a=bq+r$ then $(a,r)$ and $(a,b)$ are the same. But I want to know if this is true with the LCM as well. I think this is untrue, because if we let ...
0
votes
0
answers
30
views
Question between the proof of divisibility properties of binomial coefficient
I was reading this paper by Erdos in which he derives that there exists infinitely many $n$ such that for any primes $p,q $ where each prime is greater than $2$
$$\text{gcd}\left(\binom{2n}{n},pq\...
- 1,463
0
votes
0
answers
53
views
Why can we use $\le$ and $\mid$ equivalently in the definition of $gcd$? Can we generalize it to set that have $2$ partial orders available?
The greatest common divisor of two numbers (not both equal to $0$) is defined in $\mathbb N^*$ as the greatest element of the set of common divisors of these two numbers, with respect to the partial ...
- 969
-2
votes
1
answer
79
views
If $10|abc$, prove that either $10|ab$, $10|bc$, or $10|ac$. [closed]
Given three integers $a$, $b$, and $c$ how do I prove that if $10|abc$, it follows that either $10|ab$, $10|bc$, or $10|ac$?
I do not get much further than writing out $abc=10\cdot r$, where $r$ is ...
0
votes
2
answers
73
views
The LCM of three positive integers $X, Y$ and $Z$ is $119^2$. Find the number of ordered triplets $(X, Y, Z)$
The LCM of three positive integers $X, Y$ and $Z$ is $119^2$. Find the number of ordered triplets $(X, Y, Z)$.
My question is similar to: What is the number of ordered triplets $(x, y, z)$ such ...
- 717
2
votes
1
answer
123
views
GCD of Polynomial Roots. [duplicate]
I am sure there is an obvious answer, but suppose I have a monic polynomial with non-zero, integer coefficients given by
$$P(x) = x^n + a_{n - 1}x^{n - 1} + \cdots + a_1x + a_0$$
Veita's Formulas ...
- 123
0
votes
0
answers
20
views
Notation for taking the GCD of values in a vector
Is there any notation to take the GCD of two values in a vector? For example, if I have the following vector
$$\left[\begin{eqnarray}10\\8\end{eqnarray}\right]$$
is there a function that can be ...
- 1
0
votes
0
answers
41
views
Computing the least common multiple of the numbers 1 through n for incremental n
I notice a pattern when computing the least common multiple for the numbers 1 through n as we incrementally increase n.
The pattern is that the list of factors does ...
- 155
-1
votes
1
answer
75
views
If we know $\gcd(a,b,c)=1$, does it mean $\gcd\left(\frac{a}{\gcd\left(a,b\right)},\gcd\left(c,\frac{b}{\gcd\left(a,b\right)}\right)\right)=1$ [duplicate]
If we know $gcd(a,b,c)=1$, how to prove that $gcd\left(\frac{a}{gcd\left(a,b\right)},gcd\left(c,\frac{b}{gcd\left(a,b\right)}\right)\right)=1$? Where $a, b, c$ are any positive integers.
I have test ...
- 107
2
votes
1
answer
94
views
Finding the GCD in a function
I am currently stuck on a number theory problem.
The question is to determine the GCD of every number in the form $p^6-7p^2+6$, where $p$ is a prime number and greater than or equal to $11$.
My ...
- 79
0
votes
0
answers
27
views
if $(a-b)x=km$ ,why does $m$ divide $(a-b)$ if $x$ and $m$ are relatively prime? [duplicate]
I am reading the following proof of this proposition: Let $m, x$ be positive integers such that $\gcd(m, x) = 1.$ Then $x$ has a multiplicative inverse
modulo $m$, and it is unique (modulo $m$). There ...
- 1,701
4
votes
2
answers
150
views
Lower bound for greatest LCM
Let $k>1$ be an integer. I am looking to prove or disprove the following conjecture $(\mathscr{C}_k)$ :
There exists a constant $C_k>0$ such that for any integer $n\geq k$, if $a_1,\cdots,a_n$ ...
- 107
-1
votes
1
answer
28
views
How do I prove that $\gcd(a,b)=\gcd(-a,b)$ [duplicate]
How do I prove that $\gcd(a,b)=\gcd(-a,b)$?
Here is what I have tried:
Let $d=\gcd(a,b)$ and $d'=\gcd(-a,b)$
Then $d|a$, $d|b$, $d'|(-a)$, $d'|b$ $\implies d'|(b-a)$ and $d|(a+b)$. Then there is some ...
- 387
2
votes
0
answers
45
views
On generating certain quadruples
As part of running simulations related to this question, I had to write a program that generates quadruples $(\alpha, \beta, a, b)$ such that
$\alpha, \beta, a, b$ are all less than $n$ and
$\gcd(\...
- 3,133
2
votes
0
answers
117
views
Some conjectures based on surprising observations on magic squares
Let us restrict ourselves to odd magic squares constructed using the Uniform Step Method of Lehmer (See [Apostol51] for the construction technique).
A magic square constructed using Lehmer’s Uniform ...
- 3,133
1
vote
0
answers
43
views
Relation between Diophantine equations involving multiple sums with the modulo function and greatest common divisor function.
This one of my questions that I have as I am trying to learn about Diophantine equations, and about what I found through an OEIS search here: https://oeis.org/A360323
To generalize:
Let the function $...
- 7,286
1
vote
1
answer
87
views
Show that these ratios have numerators $\frac{1}{2} \vartheta(n) (-\exp (\Lambda (n)))$ and denominators $\exp (\Lambda (n))$ for $x=1$,
Let the Dirichlet inverse of the Euler totient function be:
$$\vartheta(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$
and compute the sum:
$$q(x,n)=\sum _{h=0}^{\infty } \left(\sum _{k=1}^n x^{h n+k}...
- 7,286
0
votes
1
answer
119
views
Common Roots of Several Multivariate Polynomials with Integer Coefficients with an Additional Property: Their GCD is Linear when Some Variables Fixed
Note: the precise formulation of the problem is at the end of the post.
$ \def \y {\boldsymbol y}
\def \z {\boldsymbol z}
\def \a {\boldsymbol a}
\def \Z {\mathbb Z} $
Consider a finite set of ...
- 6,583
1
vote
0
answers
32
views
Proof that if gcd(a, b) = 1, then lcm(a, b) = ab [duplicate]
I am trying to show the following. If $gcd(a,b) = 1$ then $lcm(a, b)=ab$. I am assuming a and b are positive integers.
I have looked at the following questions on here which are using different ...
user438803
4
votes
3
answers
198
views
Proving that a non-trivial GCD of strings $a$ and $b$ exists iff $a+b=b+a$
Firstly, assume there are two strings $a$ and $b$. Let the GCD of the two strings is the longest string which divides both. String $t$ divides $s$ iff $s = t + t + \dots + t$.
How can I show that a ...
- 502
0
votes
1
answer
66
views
Polynomials GCD over finite field [duplicate]
I'm trying to find the GCD of $x^3+2x^2+3x+4$ and $x+2$ over $\Bbb Z _5[x]$
I tried to use GCD euclidean algorithm and got the folowing:
$x^3+2x^2+3x+4 = (x^2+3)(x+2)+3$
$(x+2) = (2x)3+2$
$3=3\cdot2 + ...
- 149
0
votes
1
answer
39
views
Need help with number theory problem involving LCM. [duplicate]
Country A has elections every 4 years with its first election in 1997. Country B has elections every 5 years with its first election in 1994. When would be the first time that both the countries will ...
user907912
-1
votes
2
answers
53
views
Show that $lcm$ is associative via nesting the maximum-function [duplicate]
I found some proofs for the claim that for natural numbers $a,b,c$ it holds that
$$
\operatorname{lcm}(\operatorname{lcm}(a,b),c)
=
\operatorname{lcm}(a,\operatorname{lcm}(b,c)).
$$
I wonder whether ...
- 160
1
vote
0
answers
46
views
Proving a special case of Bézout’s Identity
I’m trying to prove the following.
Lemma.
Let $a,b,c$ be odd integers with $a>b>c\ge 1$. Then there exist positive integers $u$ and $v$ of opposite parity such that $a=bu-cv$. In particular, a ...
- 7,702
1
vote
2
answers
40
views
gcd(a S)= a gcd(S) (integral domain or ufd) [duplicate]
Les $A$ be an integral domain[1] and $S\subset A$. The set $gcd(S)$ is the set of elements $\delta$ satisfying the two following properties :
$\delta|s$ for all $s\in S$
if $d|s$ for all $s\in S$, ...
0
votes
0
answers
33
views
Is there a simplification of the expression $\gcd\left(a y(p-q)-x(b-p q),y(a-pq)+x(p-q)\right)$?
Following the question gcd simplification, I was trying to see if $$\gcd\left(a y(p-q)-x(a-p q),y(a-pq)+x(p-q)\right)$$ with $\gcd(x,y)=1$ can be simplified.
I tried to eliminate the variable $q$ and ...
- 33
0
votes
0
answers
28
views
Some advices with simple number theory [duplicate]
Given $x$ and $y$, let $m=ax+by$ and $n=cx+dy$, where $ad-bc=\pm1$. Prove that $(m,n)=(x,y)$.
First attempt
Given that $(x,y)\mid m$ and $(x,y)\mid n$ so $(x,y)\mid (m,n)$. Furthermore, from the ...
- 1,014
0
votes
1
answer
66
views
Is the sequence $p_n-n+1$ related to the Goldbach conjecture via the Dirichlet inverse of of the Euler totient?
I am trying to learn what the Goldbach conjecture is and I therefore ran this Mathematica program where I tried to incorporate the conjecture:
...
- 7,286
0
votes
0
answers
61
views
Integral affine functions without common factors
Let $f_1$, $\ldots$, $f_m \colon \mathbb{Z}^n \to \mathbb{Z}$ affine functions ( an affine function $f$ is of the form $f(x_1, \ldots, x_n) = \sum_{j=1}^n a_j x_j + b $, with $a_j$, $b \in \mathbb{Z}$)...
- 53.3k
0
votes
0
answers
24
views
Generalization of Bezout's lemma by induction [duplicate]
After proving the $n=2$ case, a lecturer I'm watching stated the generalization of Bezout's lemma and left the induction as an exercise. I think I can see how to prove it without induction, but with ...
- 2,206
1
vote
0
answers
37
views
Is it possible to eliminate $q$ from $\gcd\left(a (e-gq),(q^2-d)g-(e-gq)(q-p)\right)$?
Is it possible to eliminate the variable $q$ from the following gcd expression?
$$\gcd\left(a (e-gq),(q^2-d)g+(e-gq)(q-p)\right)$$
What I tried was the following:
Assuming that the gcd is $m$, I get
$$...
- 33
1
vote
0
answers
63
views
A special form of Bezout lemma
Let $a_1, a_2, ..., a_n$ be natural numbers and $d$ the gcd of all of them. Using Bezout lemma in number theory we can find integers $k_1, k_2,..., k_n$ such that $a_1k_1 + a_2k_2 + ... + a_nk_n = d$.
...
- 33
1
vote
1
answer
43
views
Number of steps in subtractive Euclidean algorithm
Given 2 non-negative integers a, b that range between (1 and 1e9), let c = |a - b| and after calculating c let a = b, b = c then recalculate c. what is the number of operations needed for c to reach 0....
0
votes
1
answer
64
views
Artin Corollary 2.3.9
I'm a bit confused on Artin's proof of Corollary 2.3.9. After defining the $\gcd$ of integers $d = \gcd(a,b)$ by $\mathbb{Z} d = \mathbb{Z} a + \mathbb{Z} b$ and $m = \text{lcm}(a,b)$ by $\mathbb{Z} m ...
- 2,206
-1
votes
1
answer
78
views
A number when divided by 2,3,4,5,6 leaves remainder 1,2,3,4,5 respectively but when its divided by 11 the remainder is 0. FIND THE NUMBER [duplicate]
A number when divided by $2,3,4,5,6$ leaves remainder $1,2,3,4,5$ respectively but when its divided by $11$ the remainder is $0$. FIND THE NUMBER
I tried taking LCM of $2,3,4,5,6$ and subratcing by $1(...
- 15
0
votes
0
answers
37
views
Is $\gcd(a^n-1,a^nm) = \gcd(a^n-1,m)?$ [duplicate]
I came across this procedure while trying to solve $gcd((2^{100})-1,(2^{120})-1))$, the procedure yielded correct result.
E.g
$gcd((2^{120})-1,2^{100}-1))$
=$gcd((2^{100})-1,2^{120}-2^{100}))$
= $gcd((...
- 11
0
votes
0
answers
39
views
Using Chinese Remainder theorem to find number of solutions of modular exponentiation mod composite number [duplicate]
I am struggling to understand a simple fact that should follow from the Chinese remainder theorem. Suppose we have a system of equations.
$$
x^n = 1 (mod\ p)
$$
$$
x^n = 1 (mod\ q)
$$
Where $p, q$ are ...
0
votes
0
answers
55
views
If $\gcd(a,bc)=d$, we can say that $d|a$ and $d|bc$ but what about $d|b$, $d|c$ individually? [duplicate]
I am learning about the proof of the theorem:
If $(b,c)=1$, then $(a,b)(a,c)=(a,bc)$. I have completed more than half of the theorem proof but at the end
I let $(a,bc)=d$, and i know that $d \mid a,d \...
0
votes
0
answers
48
views
Figuring out $\gcd(5a+3,4a+7)$ for $a>0$ [duplicate]
I am having a lot of trouble with a GCD problem. The problem is find $\gcd(5a+3,4a+7)$ for $a>0.$ I have been working on this for quite a while now and have the following issues:
I first tried to ...
- 349
0
votes
0
answers
30
views
Congruence equation $v^q \equiv a \pmod p $
I am reading a text on number theory, but I am confused about the following.
Let $a$ be neither $\pm 1$ nor a perfect square. Suppose $h$ is the largest positive integer such that $a$ is a perfect $h$...
- 53