How do I show that $\{1,4,7,13\}$ is closed under multiplication $\mod {15}$?
I know it's closed. Is there a rigorous way to show it?
Asked
Active
Viewed 534 times
2 Answers
2
Since there are only $4$ elements, one of which is $1$ (so $1$ multiplied any element $a$ in the set is equal to $a$, which is clearly in the set, and since multiplication is commutative in $\mathbb Z \pmod{n}$, there are really only six products remaining to check for $a\cdot b$ for $a, b \in \{4, 7, 13\}.$ That's plenty rigorous:
$4 \cdot 7 \pmod {15},\quad 4 \cdot 13 \pmod{15}, \quad 7\cdot 13\pmod{15}$
and also: $ 4^2 = 16 \pmod {15},\quad 7^2 = 49 \pmod{15}, \quad 13^2 = 169 \pmod {15}$
If and only if these products, mod $15$ are all in the given set $\{1, 4, 7, 13\},$ then the set is closed under multiplication modulo $15$.
amWhy
- 209,954
-
1And $4\cdot4\pmod {15}$, $7\cdot7\pmod{15}$, $13\cdot13\pmod{15}$. – peterwhy Sep 27 '13 at 23:19
2
A shortcut is to notice that each element is a power of $7$. That is, $7^0 \equiv 1 \operatorname{mod} 7$, $7^1 \equiv 1 \operatorname{mod} 7$, $7^2 \equiv 4 \operatorname{mod} 7$, and $7^3 \equiv 13 \operatorname{mod} 7$. Then if $a, b \in \{1, 4, 7, 13\}$, there are $i, j \in \{0, 1, 2, 3\}$ such that $7^i\equiv a \operatorname{mod} 7$ and $7^j \equiv b \operatorname{mod} 7$. Then $7^i7^j \equiv ab \operatorname{mod} 7$ but also $7^i7^j \equiv 7^k \operatorname{mod} 7$ where $k \in \{0, 1, 2, 3\}$ satisfies $i + j \equiv k \operatorname{mod} 4$. Therefore $7^k \equiv ab \operatorname{mod} 7$ and hence $ab \in \{1, 4, 7, 13\}$.
Michael Albanese
- 99,526
-
I think checking three products in this case is the shortcut here. Your shortcut invovles evaluating how many products, mod n? I agree that the method is the route to go if given more complicated sets. – amWhy Sep 27 '13 at 22:33
-
@amWhy: I think you are right, but if there were say six elements in the set rather than four, the cyclic approach (if it applied) would probably be more appealing. – Michael Albanese Sep 27 '13 at 22:35
-