Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I have a question on this proof given by Furstenberg proof on the infinitude primes. I am a non-mathematician with some basic knowledge on set theory and topology.
Define for $a,b\in\mathbb{Z}$ where $a\neq0$ the set $$S(a,b)=\{an+b:n\in\mathbb{Z}\}.$$
The Wikipedia entry says that the identify $$S(a,b)=\mathbb{Z}\setminus\bigcup_{j=1}^{a-1}S(a,b+j)$$ holds for all $a,b\in\mathbb{Z}$ where $a\neq0$. I do not see why this is the case. Can someone help me out?
If $x\in S(a,b)$ then $x=an+b$ for some $n\in \mathbb Z$. Then clearly $x\in \mathbb Z$, so we just need to show that $$x\notin \bigcup _{j=1} ^{a-1}S(a,b+j).$$ Suppose to the contrary that this was not the case. Then $x\in S(a,b+j)$ for some $1\le j\le a-1$, and thus $x=am+b+j$ for some $m\in \mathbb Z$. But then we get that $an+b=am+b+j$ which yields $a(n-m)=j$. This is impossible since $1\le j\le a-1$. So, this argument shows that $$S(a,b)\subseteq \mathbb Z-\bigcup_{j=1}^{a-1}S(a,b+j).$$
The proof of the other inclusion is similar.
Notations as in the question body.
Hint: For any integer $n$, there is a unique integer $1\le m\le a$ such that $a\mid (n-m)$.
And $n\in S(a,b) \iff a\mid (b-m)$ as well.
So, if $n\not\in S(a,b)$, then $a\not\mid (b-m)$, while $a\mid (b+j-m)$ for some $j$.
Can you take from here?
Thanks and regards.
