35. Let $a_{1}, a_{2}, a_{3}, \ldots$ be the sequence of all positive integers that are relatively prime to 75, where $a_{1}<a_{2}<a_{3}<\cdots$. (The first five terms of the sequence are: $a_{1}=1, a_{2}=2, a_{3}=4, a_{4}=7, a_{5}=8$.) Find the value of $a_{2008}$.
35. Answer: 3764
Let $U=\{1,2,3, \ldots, 74,75\}$ be the set of integers from 1 to 75 . We first find the number of integers in $U$ that are relatively prime to $75=3 \times 5^{2}$. Let $A=\{n \in U: 3$ is a factor of $n\}$ and $B=\{n \in U: 5$ is a factor of $n\}$. Then $A \cup B$ is the set of integers in $U$ that are not relatively prime to 75 . Note that $|A|=25,|B|=15$ and $A \cap B|=|\{n \in U: 15$ is a factor of $n\} \mid=5$. By the principle of inclusion-exclusion, $|A \cup B|=|A|+|B|-|A \cap B|=35$. Therefore the number of integers in $U$ that are relatively prime to 75 is $|U|-|A \cup B|=75-35=40$. Thus
$$
a_{1}=1, a_{2}=2, a_{3}=4, a_{4}=7, a_{5}=8, \ldots, a_{40}=74 \text {. }
$$

Now by division algorithm, any non-negative integer can be written uniquely in the form $75 k+r$ for some integers $k$ and $r$, where $k \geq 0$ and $0 \leq r \leq 74$. Note that $\operatorname{gcd}(75 k+r, 75)=1$ if and only if $\operatorname{gcd}(r, 75)=1$. Therefore the sequence $\left\{a_{n}\right\} n \geq 1$
can be written in the form $a_{n}=75 k+a_{i}$, where $k \geq 0$ and $1 \leq i \leq 40$. Indeed, $k$ is given by $k=\left\lfloor\frac{n}{40}\right\rfloor$ and $i$ is the remainder when $n$ is divided by 40 . Thus for $n=$ 2008, $k=\left\lfloor\frac{2008}{40}\right\rfloor=50$ and $i=8$. Hence
$$
a_{2008}=75 \times 50+a_{8}=3750+14=3764 \text {. }
$$