# Tag Info

## Hot answers tagged greatest-common-divisor

4

Since the $\gcd$ has to be a divisor of $7x-y$ and $x+2y$, it has to divide twice the first plus the second, or $15x$. It also has to divide the $7$ times the second minus the first, or $15y$. Therefore, it has to divide $\gcd(15x,15y)=15$. Thus the four possible values are $1,3,5,15$ obtained on the pairs e.g $(2,1),(1,1),(1,2),(4,13)$.

4

In order for the greatest common factor of an integer $n$ and $36$ to be $1$, $n$ and $36$ must share no prime divisors. The prime divisors of $36$ are $2$ and $3$. Thus, the question now becomes: How many integers $1 \leq n \leq 1000$ are not multiples of $2$ or $3$? This is fairly easy to compute by looking at the compliment and utilizing the ...

3

In the proof, I will use the following theorem: If a prime p divides a*b then p either divides a or b or both Now the proof Say by way of contradiction gcd(an,bm) = k > 1 Recall for all integers k greater than 1, there is a prime p such that p divides k. let p be such a prime. k is the gcd of an and bm thus k divides an and bm p divides k thus p divides ...

3

Consider the sets of quadruples of integers $$Q(n)=\{(i,j,k,l) : 1\leqslant i<j<k<l\leqslant n\},\\ Q(n,d)=\{(i,j,k,l)\in Q(n) : \gcd(i,j,k,l)=d\}$$ for $1\leqslant d\leqslant n$. Clearly we have $$|Q(n)|=\binom{n}{4},\quad Q(n)=\bigcup_{d=1}^{n}Q(n,d),\quad Q(n,d)=dQ(\lfloor n/d\rfloor,1)$$ (where, for the last one, $d(i,j,k,l):=(di,dj,dk,dl)$ and $... 3 Since$36 = 2*2*3*3$,$\gcd(n,36) = 1$iff$n$is not divisible by$2$or$3$. Hence First we find the number of integers$< 1000$which are divisible by$2$or$3$. The we will subtract this number from$999$to get our required answer. No. of integers$< 1000$which are divisible by$2 = [999/2] = 499$No. of integers$< 1000$which are ... 3 Cancelling$\,d = (a,b)\,$from both sides reduces it to the case where$\,(a,b) = 1.\,\,$Then it becomes$\, 2 = (a-b,\,a+b)\,$for$a,b\,$odd and coprime. Proof:$ $clearly$\,2\mid a-b,a+b\,$by$\,a,b\,$odd. Conversely$\,c\mid a-b,a+b\,\Rightarrow\, c\mid 2a,2b\,\Rightarrow\, c\mid (2a,2b)=2(a,b)=2.\ $QED Alternatively:$\,a\!+\!b,\,a\!-\!b\,$... 2 The proof is essentially the same as for integers - descent using (euclidean) division with remainder. To compute the Bezout identity for$\,\gcd(f,g)\,$note that the set$I$of polynomials of the form$\, a f + b g $is closed under addition and scaling so it is closed under remainder = mod, since that is a composition of such operations::$f_i\bmod g_i =...

2

We can solve for any integer $A$, not just for primorial divided by something, and proof is clearly easier. Here, we should state that, for any positive number $m$, there is a number $x$ in $[m, m+A)$ which $gcd(x(x+2), A) = 1$. The necessary/sufficient condition for $gcd(x(x+2), A) = 1$ is, $gcd(x, A)=1$ and $gcd(x+2, A) = 1$. It is obvious that ...

2

You do not need GCD or LCM at all here. The tile that will fit is the one whose length evenly divides both the room's dimensions. $10$ cm doesn't divide into $216$ cm (the room length, converted from metres), and neither does $18$ cm divide into $120$ cm (the width), so the tile of $12$ cm fits, with sides of $10$ and $18$ tiles.

2

The first key is: Theorem 1: If $a_1,\cdots,a_k$ are positive integers which are pair-wise relatively prime (that is, $\gcd(a_i,a_j)=1$ when $i\neq j$) we have that $$\operatorname{lcm}(a_1,\dots,a_k)=\prod_{i=1}^{k}a_i$$ The second key is: Theorem 2: if $a_1,\cdots,a_k$ are positive integers then there are pair-wise relatively prime integers $a_1',\... 2$ D=(a,b)$so that$D|a,\ D|b,\ 2D=(2a,2b)$and$D$is odd Hence$D|a+b,\ D|a-b$so that$D|(a+b,a-b)$Since$a+b,\ a-b$are even,$2D|(a+b,a-b)$When$D'=2kD|(a+b,a-b),\ k>1$, then $$2kD=D'|(a+b)-(a-b)=2b ,\ kD|b$$ Similarly,$kD|a$so that it is a contradiction to$D=(a,b)$2 Let$D=\gcd(2a,2b)$and$d=\gcd(a+b,a-b)$Clearly$2\,|\,D$so let$D=2E$. As you note,$E=\gcd(a,b)$. It is clear that$2\,|\,d$, and it is clear that$E$is odd. To see that$E\,|\,d$we remark that$E$must divide both$a$and$b$, hence$E$divides$a\pm b$and we are done. 2 Good work so far. The "problem" with the first solution,$(\alpha, \beta) = (-2, 1)$, is that the$-2$is negative. And so you add$(4, -2)$to it to get a new solution$(4, -1)$, and now the first entry is positive and you're good to go. Let me answer in two ways from here: how do you find$(p, q) = (4, 2)$, the "thing to add"? Well, you know that$\...

2

Let us consider the numbers that can be formed by $\alpha-1$ additions: \begin{align} \alpha =1 \text{ gives }& \mathcal{A}_1 =\{a,a+1,\ldots, a+(b-a)\}\\ \alpha =2 \text{ gives } & \mathcal{A}_2 =\{2a,2a+1,\ldots, 2a+2(b-a)\}\\ \alpha =3 \text{ gives } & \mathcal{A}_3 =\{3a,3a+1,\ldots, 3a+3(b-a)\}\\ &\vdots\\ \text{In general, } \alpha \...

2

Not necessarily directly. Because: $$\gcd(k,a(b-f))\geq a\tag{1}$$And,$$\gcd(k,ag)\geq a\tag{2}$$ And, $$\gcd(a(b-f),ag)\geq a\tag{3}$$ Gets us an upper bound on a, unless k has just 1 divisor less than this (1 is a divisor trivially sadly) we can't get an exact value yet. But, putting each possible a value through a similar test might help. Especially, if ...

1

Well, you know it is a multiple of $251$. $4036 = 16*251+20$ so $a$ is at most $256*16$. So $a = 251*b$ where $b \le 16$. $2008 = 8*251$. So $b$ and $8$ can not have any factors in common so $b \ne 16$. (Note: $\gcd(2008, 251*16) = 2008$) If $b=15$ then $b$ and $8$ don't have any factors in common. ANd if we test it: $\gcd(15*251, 2008)= \gcd(15*251, ... 1 Bézout's theorem states that if$\gcd(a,b)=d$, then exists some$p,q \in \mathbb{Z}$such that: $$ap+bq=d$$ then, you have to multiply by$\frac{n}{d}$: $$a\left( \frac{pn}{d} \right) + b\left( \frac{qn}{d} \right) = n$$ and notice that: $$a\left( \frac{pn}{d}{{\color{red} {-1}}} \right) + b\left( \frac{qn}{d}+{{\color{red} {\frac{a}{b}} }} \right) = n... 1 If you start with a\neq b (i.e. if your starting set contains more than one number) then the set of numbers that "can be formed" will always be cofinal in the natural numbers (i.e. there will always be a n s.t. every m>n could be obtained via additions). To see this, assume you start from \{n,n+1\}. Notice that if you consider the possible ... 1 Your updated original statement & proof looks correct. Regarding your main question about the distribution of the values of x where \gcd(x(x+2),p\#) = 1 for various primes p, I'll first provide an argument why there's actually very likely no upper bound on the maximum number in any single sub-range, and then give you an example where there are 3 ... 1 If you are still interested in a solution using GCD: In order to fit exactly for both walls it is necessary for the side length of a tile to divide the GCD of 120 and 216:$$(120,216) = 24 \Rightarrow 12 \mbox{ is the fitting tile side}$\$

Only top voted, non community-wiki answers of a minimum length are eligible