Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [greatest-common-divisor]

The greatest common divisor of two or more integers is the largest integer that divides all of them (if it exists).

0
votes
0answers
12 views

Lcm, hcf simple question

Jack needs to pack 48 pencils, 24 pens and 20 ballpoints in boxes. All boxes are identical. What is the largest number of boxes that can be packed? And what will be the number of stationary items in ...
0
votes
0answers
40 views

range of sum in “the polynomial $X^2+Y^4$ captures its prime”

I am reading section 12 (Flipping Moduli) of the paper "The polynomial $X^2+Y^4$ captures its primes". At page 997, just below equation (12.7) we start estimating the following sum $$ V(f,g)=\sum_d f(...
3
votes
1answer
39 views

Why $\mathbb{C}(f(t),g(t))=\mathbb{C}(t)$ implies that $\gcd(f(t)-a,g(t)-b)=t-c$, for some $a,b,c \in \mathbb{C}$?

Assume that $f(t),g(t) \in \mathbb{C}[t]$ satisfy the following two conditions: (1) $\deg(f) \geq 2$ and $\deg(g) \geq 2$. (2) $\mathbb{C}(f(t),g(t))=\mathbb{C}(t)$. In this question it was ...
5
votes
0answers
36 views

If $1\le a_1<\cdots<a_n\le 2n$ satisfy $\operatorname{lcm}(a_i,a_j)>2n$ for $i\ne j$, is $a_i>\frac{2n}{3}$ for all $i$?

If integers $1\le a_1<\cdots<a_n\le 2n$ satisfy $\operatorname{lcm}(a_i,a_j)>2n$ for $i\ne j$, is it true that $a_i>\frac{2n}{3}$ for all $i$? My attempt: Suppose that $i<j$, then $\...
1
vote
1answer
33 views

Is this proof acceptable?

Proposition: If $g$ is any common factor of $m$ and $n$ where $g,m,n \in$ $\mathbb N$ then $g \mid lcm(m,n)$ Proof: As $m \mid lcm(m,n)$ and $n \mid lcm(m,n)$ by transitivity of divisibility $g \...
5
votes
1answer
57 views

On randomly permuting digits in a large random number

Suppose you're given a natural number with $N$ digits, randomly chosen except that none of the digits are $0$. Now shuffle its digits to obtain a new $N$-digit number. What is the probability (as $N\...
0
votes
0answers
42 views

Example of a one dimensional GCD domain which is not a UFD.

I know that every UFD is a GCD domain. But every GCD domain is not a UFD. I want to make sure that a one dimensional GCD domain is not necessarily a UFD, so I'm looking for an example to confirm ...
1
vote
3answers
46 views

Prove $\gcd(n,n+2)=1$ if $n$ is odd and $2$ if $n$ is even

Prove that $\gcd(n,n+2)=1$ if $n$ is odd and $\gcd(n,n+2)=2$ if $n$ is even. My Try: So, first I took some $k$ to be even then $k$ is not the common divisor of $n$ and $n+2$. If $k|n$ and $k|n+2$ ...
4
votes
2answers
101 views

Proving fraction is irreducible

Example: The fraction $\frac{4n+7}{3n+5}$ is irreducible for all $n \in \mathbb{N}$, because $3(4n+7) - 4(3n+5) = 1$ and if $d$ is divisor of $4n+7$ and $3n+5$, it divides $1$, so $d=1$. I want to ...
0
votes
1answer
29 views

Determine the number of positive integers $a$ such that $a\mid 9!$ and gcd $(a, 3600)=180$.

Determine the number of positive integers $a$ such that $a\mid 9!$ and gcd $(a, 3600)=180$. What I know as of now is that $180\mid 9!$ and that $180\le a\le9!$. The prime factorization of 180 is $(...
0
votes
1answer
21 views

Which is the gcd of 2 numbers which are multiplied and the result is 600000?

When 2 numbers are multiplied the result is 600000.Which is the greatest common divisor? I think it might be 200.but also might be number 1.Can you help me please?
0
votes
0answers
36 views

Specific question on lcm and gcd of rings.

I can't prove this statement: Let $a_1,a_2,...,a_n$ and $b_1,b_2,...,b_n$ be non zero elements of an integral domain $R$ such that $a_1b_1=a_2b_2=\cdots=a_nb_n=x$ If $gcd(ra_1,ra_2,...,ra_n)$ exists ...
0
votes
1answer
26 views

If $g = gcd(a,b)$ prove (a,b)=(g). Furthermore, if $k = lcm(a,b)$ prove that $(a)\cap(b) = (k)$

$a,b \in \mathbb{Z}$. $(a,b),\hspace{0.4mm}(g)$ and $(k)$ are principle ideals I'm new to this kind of problems, so I don't even know how to start it. Some help would be appreciated.
1
vote
1answer
37 views

If $m, n>0$ and $\gcd(m, n) =d$, then $\gcd(a^m-1, a^n-1) =a^d-1$.

This question has already answered here in other topics, but all answers that I read have some techniques like congruence and fermat numbers and the book which I am reading shows this question in ...
0
votes
0answers
23 views

Help proving divisibility involving gcd: if $a\mid c$ and $b\mid c$ and $\gcd(a,b)=1$, then $ab\mid c$ [duplicate]

I am currently stuck proving the following implication: For all integers $a,b,c$, if $a\mid c$ and $b\mid c$ and $\gcd(a,b)=1$, then $ab\mid c$ Since $a\mid c$ and $b\mid c$, $\exists k,l\in\Bbb{Z}$ ...
1
vote
1answer
20 views

Product of gcd and lcm for multivariate polynomials

This maybe trivial but I don't know how to conclude the proof. Consider the ring of multivariate polynomials with field coefficients $K[X_1,\dots,X_n]$. Take two nonzero polynomials $F$ and $G$ and ...
2
votes
1answer
26 views

Given an odd integer, $a$ does $\gcd(a,p-1)=1$ has infinitely many prime $p$ solutions?

Given an odd integer, $a$ does $\gcd(a,p-1)=1$ has infinitely many prime $p$ solutions? One can argue that there are infinitely many numbers $x$ satisfies $\gcd(a,$x$)=1$. How to argue that there ...
0
votes
0answers
13 views

Creating inputs that make a subtraction-based GCD algorithm slow

I have a GCD algorithm that is based on comparison and subtraction. The principle looks like this: ...
2
votes
0answers
14 views

Removable singularities for rational functions with floating point coefficients

Suppose I have given a rational function $r(x)=p(x)/q(x)$ where $p$ is a degree $m$ polynomial and $q$ is a degree $n$ polynomial (over the real numbers) and the coefficients of p and q are ...
2
votes
1answer
37 views

What proportion of the positive integers satisfies $\gcd(n^2,\sigma(n^2))>\sigma(n)$, where $\sigma$ is the sum-of-divisors function?

The title says it all. What proportion of the positive integers satisfies $\gcd(n^2,\sigma(n^2))>\sigma(n)$, where $\sigma$ is the sum-of-divisors function? I tried using Sage Cell Server to ...
0
votes
0answers
30 views

Another GCD proof [duplicate]

If $gcd(a, b) = 1$ and $n$ is a prime then prove that $gcd(\frac{a^n + b^n}{a + b}, a + b) = 1$ unless $a + b$ is a multiple of $n$
4
votes
3answers
50 views

Connection between GCD and LCM of two numbers

These two exercises I encountered recently seem to develop some type of connection between GCD and LCM I can't quite figure out. Exercise 1: Find all the numbers $x$ and $y$ such that: $a) \ ...
0
votes
1answer
181 views

When does $(a,b)=(\gcd(a,b))$ hold?

I had a look here to understand why $K[X,Y]$ is not a PID. So one of the conclusions was that $(x,y) \neq (1) = \gcd(x,y)$, but I thought that $(a,b)=\gcd(a,b)$ was always true so obviously I was ...
0
votes
1answer
38 views

How to prove an equivalence of two equations?

Task: Prove that . $s \cdot a + t \cdot b = c$ has a solution $s, t \in \mathbb{Z}$ iff $c$ is a multiple of $ gcd(a,b) $. I’m not sure whether my proof is correct or not, so pleas have a look on it: ...
1
vote
1answer
15 views

Non-integral domain for which there still exists a gcd for each pair of elements.

Does there exists an non-integral domain for which we still have a gcd for each pair of elements (a,b)? Here, when I say gcd, I mean the definition of gcd for commutative rings given by wikipedia.
1
vote
2answers
93 views

First International Olympiad, 1959

The problem is: Prove that $\dfrac{21n+4}{14n+3}$ is irreducible for every natural number $n$. Can anyone please give me a hint?
0
votes
1answer
45 views

Showing that a greatest common divisor must be 1 or 2 using pigeonhole principle

I need to prove that for any $S \subset \{1,2,...,2018\}$ with $|S|=673$, it follows that $\exists\,a,b \in S$ such that $gcd(a,b)<3$. I can see the obvious application of pigeonhole principle ...
0
votes
0answers
38 views

Prove $\frac{ab}{m} = \gcd(a,b)$ when $m=\operatorname{lcm}(a,b)$, for all natural numbers $a$ and $b$.

Prove $\frac{ab}{m} = \gcd(a,b)$ when $m= \operatorname{lcm}(a,b)$ for all natural numbers $a$ and $b$. I should be able to prove this using only basic rules of $\gcd$ and lcm. I instead let $m$ be a ...
0
votes
1answer
21 views

Bezout's identity: which half is larger? [closed]

Bezout's identity: Let a and b be integers with greatest common divisor d. Then, there exist integers x and y such that ax + by = d. Is it true that if a > b then ax < by? Is there a proof for ...
0
votes
0answers
45 views

Prove that, $\textrm{LCM}(\textrm{GCD}(m,x),\textrm{GCD}(n,x)) = \textrm{GCD}(\textrm{LCM}(m,n),x)$

I want to show that for $m,n,x \in \mathbb{Z}$, \begin{align*} \textrm{LCM}\left(\textrm{GCD}\left(m,x\right),\textrm{GCD}\left(n,x\right)\right) = \textrm{GCD}\left(\textrm{LCM}\left(m,n\right),x\...
1
vote
1answer
66 views

When do Co-Primes have a common factor?

If a and b are co-primes and $n$ is a prime then prove that $\frac{a^n + b^n}{a+b}$ and $(a+b)$ have no common factors unless $(a+b)$ is a multiple of $n.$ I am unable to proceed, please help.
0
votes
0answers
32 views

In which rings are gcd and lcm defined?

Greatest common divisor and least common multiple exist for elements of integers, univariate polynomial ring and multivariate polynomial rings. So in most general manner, in which rings do gcd and ...
0
votes
1answer
43 views

Finding the HCF

Find $(a^{2^m}+1, a^{2^n}+1)$ when a is odd and a,m,n are positive integers and m is not equal to n. I know that the hcf is a multiple of two but I can't prove that it is 2 which is the answer. Plz ...
0
votes
0answers
54 views

On the quantity $\sigma(\frac{n^2 \sigma(n^2)}{D(n^2)})$ when $q n^2$ is an odd perfect number with special prime $q$

Denote the sum of the divisors of $x \in \mathbb{N}$ by $\sigma(x)$. Also, denote the deficiency of $x$ by $D(x)=2x-\sigma(x)$. If $m$ is odd and $\sigma(m)=2m$, then $m$ s called an odd perfect ...
0
votes
1answer
22 views

What thoughts should I be having when proving the Euclidean Division Algorithm?

Given $m > 0 \mathbin{|} m ∊ ℕ$ and $n > 0 \mathbin{|} m ∊ ℕ$, let's say $m \leftarrow 50$ $n \leftarrow 20$ Number Theory tells us that any positive integer can be written as a product of ...
0
votes
0answers
57 views

Proof verification: If $gcd(n,9)=3$ then $gcd(n^2,9)=9$, $p∣n \implies p∣n^2$, $p∣n^2\implies p∣n$.

1. gcd$(n,9)=3$ then gcd$(n^2,9)=9$ 2. Let $p$ be a prime and $n \in \mathbb{N}$, if $p∣n$ then $p∣n^2$. 3. Let $p$ be a prime and $n \in \mathbb{N}$, if $p∣n^2$ then $p∣n$. I'm not sure about ...
0
votes
0answers
32 views

Greatest Common Divisor in a ring definition

We were given this defintion in our Algebra $2$ course: Definition $4.1$: Let $R$ be a commutative ring and $a, b\in R$. An element $d \in R$ is called a greatest common divisor, $\operatorname{...
0
votes
2answers
40 views

Prove if $n\mid ab$, then $n\mid [\gcd(a,n) \times \gcd(b,n)]$

Prove if $n\mid ab$, then $n\mid [\gcd(a,n)\times \gcd(b,n)]$ So I started by letting $d=\gcd(a,n)$ and $e=\gcd(b,n)$. Then we have $x,y,w,z$ so that $dx=a$, $ey=b$,$dw=ez=n$ and we also have $s$ so ...
1
vote
0answers
24 views

Prove that the there exists a single Reduced residue system.

Let $m$ and $n$ be two integers such that $(m, n) = 1$ and $\phi(m) =\phi(n) $. Then there exists a single residue system which is congruent both modulo $m$ as well as $n$. What i know is that if $(m,...
1
vote
2answers
22 views

Bezout's identity on $F[x]$ with constraints

I have some issues with solving this exercise: Prove: Let $F$ be a field. If $f,g∈F[x]$ are relatively prime and not both constant, then there exists $a,b∈F[x]$ such that $af+bg=1$ and $\deg(a)<\...
1
vote
0answers
70 views

How can I calulate $\gcd(ab,c)$?

It is known that: If $\gcd(a,b)=1$, then $\gcd(ab,c)=\gcd(a,c) \cdot \gcd(b,c)$. Let $p$ be a prime number such that $p\mid a$. Then $v_p(b)=0$ (since $\gcd(a,b)=1$), $\min\{v_p(b),v_p(c)\}=0$ ...
0
votes
2answers
66 views

Find $\gcd(3^{20} + 3, 3^{21} +6)$

Find $\gcd(3^{20} + 3, 3^{21} +6)$ I am honestly so confused, I know $3$ divides both terms but am unsure if that's the $\gcd$.
0
votes
1answer
18 views

Finding a greatest common divisor

Find a GCD of number $A_0,A_1,\cdots,A_{2013}$ if $A_n=2^{3n}+3^{6n+2}+5^{6n+2}$ where $n=0,1,\cdots,2013$ I have no idea can you help me. Only what I can see that they have the same degree $3n$ and ...
-1
votes
1answer
38 views

How do I prove that, if $a$ divides $b$, then $a^n$ divides $b^n$? [duplicate]

How would I prove the following? If $a$ divides $b$, then $a^n$ divides $b^n$.
4
votes
1answer
86 views

If $x$ and $y$ are solitary numbers satisfying $\gcd(x,y)=1$, under what conditions does it follow that $xy$ is also solitary?

Let $\sigma(z)$ denote the sum of divisors of $z \in \mathbb{N}$. Denote the abundancy index of $z$ by $I(z) = \sigma(z)/z$. If the equation $I(z)=I(a)$ has the lone solution $z=a$, then $a$ is said ...
2
votes
2answers
25 views

Let $D$ be a PID and $a$ and $b$ be nonzero elements of $D$. Prove that there exist elements $s$ and $t$ in $D$ such that $\gcd(a, b) = as + bt$.

Let $D$ be a principal ideal domain and $a$ and $b$ be nonzero elements of $D$. Prove that there exist elements $s$ and $t$ in $D$ such that $\gcd(a, b) = as + bt$. I would like to use some ...
0
votes
0answers
17 views

Calculating Bezout coefficients and gcd for two numbers that divide evenly with no remainder.

I'm working to better understand Bezout coefficients and gcd. I can hand calculate down through the Extended Euclidian Algorithm to calculate the gcd and then gather terms effectively to determine the ...
2
votes
3answers
112 views

Solve the equation $x^4+x^3-9x^2+11x-4=0$ which has multiple roots.

Q:Solve the equation $x^4+x^3-9x^2+11x-4=0$ which has multiple roots.My approach:Let $f(x)=x^4+x^3-9x^2+11x-4=0$.And i knew that if the equation have multiple roots then there must exist H.C.F(Highest ...
1
vote
1answer
216 views

Find $G\left(10^{11}\right)$

Given a function $G(N)$ defined as $$G(N)=\sum_{j=1}^{N}\sum _{i=1}^{j} GCD(i,j)$$ where $GCD$ is Greatest Common Divisor of two numbers If it is known that $G(10)=122$, Find Value of $G(10^{11})$ ...
2
votes
1answer
91 views

How can I find $\gcd(n^a-1,m^a-1)$?

From Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ , we have $$\gcd(a^n-1,a^m-1)=a^{\gcd(n,m)}-1$$ for every positive integers $a,n,m$. I reversed $a$ with $n,m$, and I had this question: ...