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?

  • 1
    $\begingroup$ +1. Very nice proof of the infinitude of primes. I had to solve this problem in my topology class and was rather surprised about the connection of topology to such a thing like the infinitude of primes. $\endgroup$ – math Apr 7 '13 at 11:31

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.

  • $\begingroup$ thank you for your assistance $\endgroup$ – kevin Apr 7 '13 at 10:26

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.