(Solved): Let \( S \) be the set of all positive integers of the type \( 3 n+1 \). So \( S=\{1,4,7,10, \ldot ...

Let \( S \) be the set of all positive integers of the type \( 3 n+1 \). So \( S=\{1,4,7,10, \ldots\} \). (a) Show that \( S \) is closed under multiplication. That is, the product of any two numbers in \( S \) is in \( S \). You need to show that \( (3 m+1)(3 n+1)=3 q+1 \) for some integer \( q \). (b) List all the divisors of 40 that are in \( S \). List all the divisors of 100 that are in \( S \). List all the common divisors of 40 and 100 that are in \( S \). (c) Show that in \( S \), \( \operatorname{gcd}(40,100)=10 \), and that this number is not a multiple of all other common divisors of 40 and 100 . Comment: This does not happen in the set of all positive integers, where the gcd is always a multiple of all other common divisors. (d) Let \( k=4, a=10 \), and \( b=25 \). Show that in \( S \), \( \operatorname{gcd}(k a, k b)=\operatorname{gcd}(40,100)=10 \), but \( k \operatorname{gcd}(a, b)=4 \operatorname{gcd}(10,25)=4 \). So the formula \( \operatorname{gcd}(k a, k b)=k \operatorname{gcd}(a, b) \) fails in \( S \). Exercise 4 shows us that only using the closure of the set of positive integers under multiplication will not be enough to prove that the gcd is always a multiple of all other common divisors, and that the formula \( \operatorname{gcd}(k a, k b)=k \operatorname{gcd}(a, b) \) holds in the positive integers. We have to go beyond the multiplicative world, even though the gcd is defined in this world.