Can someone help me prove the following proposition?

Question

Let S be the set of positive integers defined by

Basis step: 1 ∈ S.

Recursive step: If n ∈ S, then 3n + 2 ∈ S and n^2 ∈ S.

a) Show that if n ∈ S, then n ≡ 1 (mod 4).

b) Show that there exists an integer m ≡ 1 (mod 4) that does not belong to S.

I do not know how to proceed with this proof and our professor didn't do similar examples in class. Can you please explain me the steps?

Answer 1

a) This can be done by induction. Clearly, $1\equiv1\pmod4$. And, if $n\equiv1\pmod4$, then:

• $3n+2\equiv3\times1+2\pmod4\equiv1\pmod4$
• if $n=4l+1$, $n^2=16l^2+8l+1\equiv1\pmod4$

b) Take the number $9$. Of course, $9\equiv1\pmod4$. But the first elements of $S$ are $1,5,17,25\ldots$ and so $9\notin S$. And neither is $13$.