Integers divisible by 5 but not divisible by 7 are countably infinite

Question

I have searched for the answer to this question online and have come across some answers, however, I am struggling to understand it. How would I come up with a function for which the integers are multiples of 5 but not multiples of 7? I also want to show a one-to-one correspondence with the set of positive integers, so that I can prove it is countably infinite. This is what I have so far:

$$ f : \mathbb{Z+} \to \mathbb{P} \quad\text{defined by}\quad f(n) = \begin{cases} 5(\frac{n}{2}) & \text{if $n$ is even, and} \\ 5(\frac{n-1}{2}) & \text{if $n$ is odd.} \\ \end{cases} $$

where P is the set of integers that are multiples of 5. Now I am struggling to alter it so that the multiples of 7 (35, 70, 105, ...etc) are not included. Can someone perhaps help me and show me how to prove that there is a one-to-one correspondence with the set of positive integers.

Answer 1

Note that one way to avoid factors of $7$ is to just repeatedly multiply by $5$ (why does this work?). For example, the recursive function: $$f_{n+1} = 5*f_n,\hspace{0.2in}f_1 = 1.$$ is only divisible by $5$ for any $n$, but not $7$.

Answer 2

Consider the map $f: \mathbb{N} \backslash 7\mathbb{N} \to \mathbb{N}$ given by $f(n)=n- \left \lfloor \frac{n}{7} \right \rfloor$. Then if $f(n)=f(m)$ with $n \geq m$, we have $$m-n = \left \lfloor \frac{m}{7} \right \rfloor - \left \lfloor \frac{n}{7} \right \rfloor \geq \left \lfloor \frac{m-n}{7} \right \rfloor \implies n-m \leq \left \lceil \frac{n-m}{7} \right \rceil$$ But this can only be true if $n=m$ or $n=m+1$. But if $n=m+1$, then $f(m)=f(m+1)$, and so $\left \lfloor \frac{m+1}{7} \right \rfloor = \left \lfloor \frac{m}{7} \right \rfloor + 1 \implies 7 |(m+1)$, so $m+1$ is not in the domain of $f$, showing $f$ is injective.

Further, if $n \in \mathbb{N}$, then $$f \left( n+\left \lfloor \frac{n}{6} \right \rfloor \right) = n + \left \lfloor \frac{n}{6} \right \rfloor - \left \lfloor \frac{1}{7} \left ( n+ \left \lfloor \frac{n}{6} \right \rfloor \right ) \right \rfloor = n + \left \lfloor \frac{n}{6} \right \rfloor - \left \lfloor\frac{1}{7} \left \lfloor \frac{7n}{6} \right \rfloor \right \rfloor = n + \left \lfloor \frac{n}{6} \right \rfloor - \left \lfloor \frac{n}{6} \right \rfloor = n$$

Noting our previous computations show that if $7 | (n+ \left \lfloor \frac{n}{6} \right \rfloor)$, then $f(n+ \left \lfloor \frac{n}{6} \right \rfloor - 1)=n$ as well, this shows that $f$ is surjective.

So $f$ is a bijection from $\mathbb{N} \backslash 7 \mathbb{N}$ to $\mathbb{N}$, and hence $5f^{-1} : \mathbb{N} \to 5\mathbb{N} \backslash 7\mathbb{N}$ is a bijection from the natural numbers to the multiples of $5$ coprime to $7$. Alternatively, the inverse map going the other direction is $n \mapsto f \left ( \frac{n}{5} \right )=\frac{n}{5} - \left \lfloor \frac{n}{35} \right \rfloor$.

This constructs the desired bijection explicitly as desired, but keep in mind that this is not nearly the most effective way to demonstrate that $5\mathbb{N} \backslash 7\mathbb{N}$ is countably infinite, and this is often the case. Indeed, even for this relatively simple set for which it is intuitively obvious that it is countably infinite, it is already annoying to construct the maps explicitly. A more efficient approach is one like D.B.'s-- show that it contains one countably infinite set (the powers of $5$) and is contained in another (the natural numbers themselves).

Answer 3

A simple polynomial answer, via CRT is that you want a mapping from:

$$S=\{x:x=35k+5y, y\neq7j\}$$

To the natural numbers. So map $35k+5y$ to $7k+y-k$ like so:

$$5\to1\quad10\to2\quad15\to3\quad20\to4\quad25\to5\quad30\to6\quad40\to7\ldots$$

ignore $y=7j$