Question: Which of the following are reduced modulo residue systems modulo 18?
$a. 1,5,25,125,625,3125$
$b. 5, 11, 17, 23, 29, 35$
$c. 1, 25, 49, 121, 169, 289$
$d. 1, 5, 7, 11, 13, 17$
Attempt: Our mod n is mod 18, so n = 18. Now, we need to remove the integers that aren't prime to n. Now, I know 18 is obviously not a prime because that's $3^2 \times 2$ or $ 3 \times 3 \times 2$
Our set of all integers for mod 18 is $Z_{18} ={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}$
Restricting the set to only prime numbers, we have
$Z_{18} ={1,3,5,7,11,13,17}$
I can easily see that the last choice will be the reduce modulo residue system because that's almost the exact same string as $Z_{18} ={1,3,5,7,11,13,17}$ but the three is missing. What I don't understand is how the first choice is also a reduce module residue system for mod 18 because that's $5^n$ where $n=1,2,3,4,5$, so that's first string is
$5^0,5^1,5^2,5^3,5^4,5^5$. Unless we consider the base which is $5$ and that is in the restricted set of prime numbers for $Z_{18}$.
So, how is b and c not a reduce modulo?
C is just $1^2,5^2,7^2,11^2,13^2,17^2$ and B has 6 added to each digit.
$b. 5, 11, 17, 23, 29, 35$
$5+6 = 11…11+6=17…17+6=23…23+6=29…29+6=35$
Edit: I need the co-primes of 18, so basically I need to find the primes and anything that's divisible by 18.
2 divides 18 = 9 times
3 divides 18 = 6 times
6 divides 18 = 3 times
9 divides 18 = 2 times
so 2 3 6 9 are gone.
$Z_{18} ={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}$ becomes $Z_{18} ={0,1,4,5,7,8,10,11,12,13,14,15,16,17}$.
Now for the primes… obviously, $0,4,8,10,12,14,15,16 $ aren't prime, so they're gone and now we have
$Z_{18} ={1,5,7,11,13,17}$, and that matches the last choice, but I still don't understand how the first choice is also a reduce residue system….unless I take the base only which is 5 and that's in the set? But there has got to be a better reasoning than that right?
Best Answer
We first identify one reduced residue system. Let us list all the numbers from $1$ to $18$ that are relatively prime to $18$. They are $1,5,7,11,13,17$. This happens to be the collection d). so we have identified one winner.
Now let us look at the others. For each of our given collections, find the remainders of the numbers in the collection on division by $18$. If we get $1,5,7,11,13,17$ in some order, we have a reduced residue system. If we don't, then we don't have a reduced residue system.
For example, consider the numbers $1,5,25,125,625,3125$. The first remainder is $1$, and the second is $5$. That was easy! The third remainder is $7$. You could compute the next three remainders. The numbers are getting kind of big, so we introduce a shortcut. Since the remainder of $25$ is $7$, The remainder of $5\cdot 25$ is the same as the remainder of $5\cdot 7$. This is $17$. The remainder of $5\cdot 125$ is the same as the remainder of $5\cdot 17$, which is $13$. And finally the remainder of $5\cdot 625$ is the remainder of $5\cdot 13$, which is $11$. So we did get $1,5,7,11,13,17$ in some order, and therefore the collection a) is a reduced residue system.
Note that b) is not a reduced residue system, since $23$ has the same remainder as $5$.
We leave c) to you.
After a while, you will learn some shortcuts that make the computations easier. But at this stage, the best approach is to calculate remainders.