0
$\begingroup$

I have tried to think as intersections of two lines but for $2x+3$ and $5x+7$ is failed to have integer intersections (but not sure it is enough counterexample).

Is the above generalisation correct? Can you give a counter-example, or a hint for how to prove it?

$\endgroup$
4
  • 1
    $\begingroup$ you have $ 2 * 2 + 3 = 5 * 0 + 7$. The "x" need not be the same. $\endgroup$
    – Calvin Lin
    Commented Jan 3, 2021 at 16:39
  • 1
    $\begingroup$ You assumed slightly too much. It's not that $2x+3 = 5x+7$ but rather that $2x+3 = 5y+7$ for some natural numbers $x,y$. $\endgroup$
    – Cameron Williams
    Commented Jan 3, 2021 at 16:40
  • $\begingroup$ Immediate consequence of CRT, e.g. apply the Theorem in the dupe to $\,z\equiv b\pmod{a},\ z\equiv y\pmod{x}\ \ $ $\endgroup$
    – Bill Dubuque
    Commented Jan 3, 2021 at 17:14
  • $\begingroup$ "Immediate consequence of CRT" minor additional step. CRT says $w\equiv b\pmod a; w\equiv y\pmod x$ has unique solutions $\pmod {ax}$ so there exist integers $M,N$ so that $w = aM + b=xN + y$. But it doesn't say $M,N$ are natural numbers. But that is an exceedingly minor point. ..... $w+k(ax) = a(M+kx) =x(N+ka)$ so we can add multiples of $x$ and $a$ to $M,N$ until they are both positive. $\endgroup$
    – fleablood
    Commented Jan 3, 2021 at 17:42

4 Answers 4

Reset to default
0
$\begingroup$

Thinking in terms of straight lines and looking for points of intersection where both lines have the same output for the same input is not the best analogy. It's better to think of these as unstructured unordered sets which are like bags of groceries that they have a bunch of stuff dumped in them in no particular order and an "intersection" simply means the two bags both have the same item somewhere. ("You bought mushrooms and tampons too! So did I!")

$2\mathbb N + 3 = \{5,7,9,11,13,15,17,19,21,23,25,27,29......\}$ and $5\mathbb N + 7= \{12,17,22,27,32,....\}$

Notice they both have $17$ and $27$ and $37$ etc in them. Note those numbers aren't in both for the same reason... If $17 \in 2\mathbb N+3 = \{2\color{blue}n + 3|\color{blue}nn\in \mathbb N\}$ it is because if $\color{blue}{n= 7}$ we get $2\cdot\color{blue}{7} +3=17$ which $17 \in 5\mathbb N + 7=\{5\color{red}n + 7|\color{red}n \in \mathbb N\}$ because if $\color{red}n = 2$ we get $5\cdot\color{red}2+7=17$... but we don't care why the items are in the bag, just that they are both in each of the bags.

("I bought the mushrooms as the fifth item right after the milk and a picked up the tampons at the check out counter as my last item" "Oh, not me. I went shopping just because I needed tampons so I bought the first thing. Then I thought about dinner so I bought pasta, mushrooms, and onions. Mushrooms were the third thing I bought.")

..........

So this is actually much looser.

You mus show that there exist natural number $M,K$ so that $aM + b= xK +y$ where $M,K$ can be any natural numbers and need not have any thing in common.

That would mean $aM - xK = (y-b)$. By Bezout's lemma you know we can find integers$M', K'$ so that $aM' + xK' = 1$ so if we let $M = (y-b)M'$ and $K = -(y-b)K'$ we get $aM - xK = y-b$.

Or only concern is whether or not $M,K$ are both positive. I'll let you work the details.

(Note: if $a,b \ge 0$ then $aM' + bK' = 1$ would mean only one of $M'$ or $K'$ is positive and the other is either negative or $0$.)

=====

Postsript: For the record the two sets $a\mathbb N + b$ and $x \mathbb N + y$ don't just intersect and have one item in common. They have an infinite number of items in common.

.....

Notice that every $10K + 7 = 2(5K + 2) + 3= 5(2K) + 7 \in (2\mathbb N + 3)\cap( 5\mathbb N + 7)$. So for all $K$ we have $10K + 7$ is in the intersection.

That may give you a hint to a more direct way (but not necessarily easier) way to solve it than my Bezout solution.

$\endgroup$
0
$\begingroup$

This is true, and in fact you only need the first condition $\gcd(a,x)=1$. This follows from the Chinese remainder theorem. For example, $2\mathbb N+3$ and $5\mathbb N+7$ both include all points in $10\mathbb N+7$.

$\endgroup$
3
  • $\begingroup$ is lcm, always works? $\endgroup$
    – Jale'de jaled
    Commented Jan 3, 2021 at 16:52
  • $\begingroup$ what is the general form of $a\mathbb N+b\cap x\mathbb N+y$ if $(a,x)=1$ $\endgroup$
    – Jale'de jaled
    Commented Jan 3, 2021 at 16:53
  • $\begingroup$ @Jale'dejaleuffnejale it will be $ax\mathbb N+c$ for some value of $c$. Assuming your definition of $\mathbb N$ includes $0$, there will always be a unique common point in $[\max(b,y),ax+\max(b,y))$ which will be the value of $c$. $\endgroup$
    – Especially Lime
    Commented Jan 3, 2021 at 17:02
0
$\begingroup$

Hint: Find integers $A, X$ such that $ a A +xX = y - b$.

$\endgroup$
1
  • $\begingroup$ To show $A$, $X$ exist: $gcd(x,a) = 1$, then $\alpha x+\beta a = 1$, for some $\alpha, \beta$ .Then multiply both sides by $(y-b)$. $\endgroup$
    – Aven Desta
    Commented Jan 3, 2021 at 16:47
0
$\begingroup$

First since $gcd(x,a)=1$, there exist $\alpha$, $\beta$, such that (Bézout's identity)$$\alpha x - \beta a = 1$$ Now multiply both sides by $k = b-y$.

$$(k \alpha ) x - (k \beta)a = b-y$$ $$(k \alpha ) x + y = (k \beta)a +b$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .