The set \(S\) consists of all the positive integers that leave a remainder of 1 upon division by 4.
The set \(T\) consists of all the positive integers that leave a remainder of 3 upon division by 4.
Describe in words the sets
\(S \cup T\) and \(S \cap T\).
Prove that the product of any two integers in \(S\) is also in \(S\).
Determine whether the product of any two integers in \(T\)
is also in \(T\).
Given an integer in \(T\) that is not a prime number,
prove that at least one of its prime factors is in \(T\).
For any set \(X\) of positive integers,
an integer in \(X\) (other than 1) is said to be
\(X\)-prime if it cannot be expressed as the product of
two or more integers all in \(X\) (and all different from 1).
\(\bf (a)\) Show that every integer in \(T\) is
either \(T\)-prime or is the product of an odd number of
\(T\)-prime integers.
\(\bf (b)\) Find an
example of an integer in \(S\) that can be expressed as the product
of \(S\)-prime integers in two distinct ways. [Note:
\(s_1s_2\) and \(s_2s_1\) are not counted as distinct ways of
expressing the product of \(s_1\) and \(s_2\).]
Solution:
\(S \cup T\) is the set of odd positive integers. \(S \cap T\) is the empty set.
Suppose we have two integers in \(S\), say \(4n+1\) and \(4m+1\), so \((4n+1)(4m+1) = 16nm + 4(n+m) + 1 = 4(4nm + n+m) + 1\) which clearly is in \(S\).
The product of any two integers in \(T\) is in \(S\), since \((4n+3)(4m+3) = 16nm + 12(n+m) + 9 = 4(4nm+3(n+m) + 2) + 1\)
Suppose \(p \in T\) is not prime, then it must have prime factors. They must all be odd, so they are in \(T\) or \(S\). If they are all in \(S\) then \(p\) must also be in \(S\) (as the product of numbers in \(S\)) but this is a contraction. Therefore \(p\) must have a prime factor in \(T\).
\(3, 7, 11, 19\) are all primes in \(T\). Notice therefore that any product of two of them must be \(S\)-prime. But then \((3 \times 7) \times (11 \times 19)\) and \((3 \times 11) \times (7 \times 19)\) are distinct factorisations into \(S\)-prime factors.