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