0

show that if a subset of $\big\{{1,2,...,21}\big\}$ contains an even number or contains the number $11$, then it cannot form a group under multiplication modulo $22$.

first of all it's clear that the multiplication of the two numbers $2$ and $11$ is a multiple of $22$, implies $2·11≡0 (mod\: 22)$, since the element $0$ is not a member of the given set so the group is not closed under the binary operation. but how is it possible to find all the pair of numbers which their multiplication modulo $22$ has a reminder which doesn't exist in the given set (assume I could not find $2$ and $11$).

also $2$ and $11$ does not have any inverse, means there is no element which holds in the equation $2·x≡1 (mod\: 22)$ and the same about $11$, but how we can be sure about that?

1 Answers1

0

It is enough to show that not all elements are invertible, that means the set cannot be a group with respect to this operation. How can we be sure that $2$ of $11$ are not invertible? Well, let's assume $11$ is invertible, i.e there is $x\in\{0,1,...,21\}$ such that $11x\equiv 1$(mod $22$). By definition this means that $22|(11x-1)$ and hence there is $y\in\mathbb{Z}$ such that $11x-1=22y$, or equivalenly $11x-22y=1$. But note that this equation implies that any integer which divides both $11$ and $22$ must divide $1$ and hence we get $\gcd(11,22)=1$ which is of course a contradiction. So $11$ is not invertible mod $22$.

You can do the same thing for $2$, and in general $a\in\{0,1,...,n-1\}$ is invertible mod $n$ if and only if $\gcd(a,n)=1$.

Mark
  • 39,605
  • what did you say is clear, also if we want to find the pair of the numbers (well as you said it's not necessary) but is there any way expect Cayley table? –  Jul 27 '19 at 18:49
  • Not sure what you mean by "pairs of numbers". As I wrote in the last sentence the elements in the multiplicative group are the elements such that $\gcd(a,22)=1$. So a product of such two elements is also in the multiplicative group. Of course this requires a proof but it's pretty easy. Other elements can't belong there. If you multiply $2$ elements such that at least one is not invertible mod $22$ then the product will also not be invertible. – Mark Jul 27 '19 at 18:53
  • I want to know what reminders (indeed the reminders which belong to the multiplication of two elements in the given set module &22&) are not in the set.(without using Cayley table). –  Jul 27 '19 at 19:18
  • 1
    Oh, you mean remainders? Well, the remainders which form the multiplicative group are exactly those which are relatively prime to $22$. These are $1,3,5,7,9,13,15,17,19,21$. You don't need a Cayley table. It is known that if $\gcd(a,22)=\gcd(b,22)=1$ then $\gcd(ab,22)=1$ as well. So the set of remainders which are relatively prime to $22$ is closed under multiplication. – Mark Jul 27 '19 at 19:29