Calculate 11c-5d: Solving Exercise

[evinda]

Hello! (Wave)

I am looking at the follwong exercise:

Notice that the multiplicative group $\mathbb{Z}^{*}_{10} \times \mathbb{Z}^{*}_{22}$ is cyclic and consider its generator $([a]_{10},_{22})$ with the lowest possible positive integers $a$ and $b$. Let $([a]_{10},_{22})^{33}=([c]_{10},[d]_{22}), 1 \leq c \leq 10, 1<d<22$.Which is the value of $11c-5d$ ?

$$\mathbb{Z}^{*}_{10}= \{ 1,3,7,9\}$$
$$[3]^1=[3],[3]^2=[9],[3]^3=[27]=[7], [3]^4=[3]^3 \cdot [3]=[7 \cdot 3]=[1] \checkmark $$
$$\text{So, } a=3$$

$$\mathbb{Z}^{*}_{22}= \{ 1,3,5,7,9,13,15,17,19,21\}$$

$$[3]^1=[3], [3]^2=[9], [3]^3=[27]=[6] \times$$

$$[5]^1=[5], [5]^2=[25]=[3] , [5]^3=[5]^2 \cdot [5]=[15], [5]^4=[15 \cdot 5]=[75]=[9] , [5]^5=[9 \cdot 5]=[45]=[1] , [5]^6=[5] \times $$

$$[7]^1=[7], [7]^2=[49]=[5], [7]^3=[5 \cdot 7]=[35]=[13], [7]^4=[13 \cdot 7]=[91]=[3], [7]^5=[3 \cdot 7]=[21], [7]^5=[21 \cdot 7]=[147]=[15], [7]^6=[15 \cdot 7]=[17], [7]^7=[17 \cdot 7]=[9], [7]^8=[9 \cdot 7]=[19], [7]^9=[19 \cdot 7]=[1] \checkmark $$

$$b=7$$

$$([3]_{10},[7]_{22})^{33}=([c]_{10}, [d]_{22}) \Rightarrow ([c]_{10}, [d]_{22})=([3^{33}]_{10},[7^{33}]_{22})$$

$(3,10)=1, \phi(10)=\phi(2 \cdot 5)=10(1-\frac{1}{2})(1-\frac{1}{5})=10 \cdot \frac{1}{2} \cdot \frac{4}{5}=4$

$$\text{ So from Euler's Theorem: } 3^4 \equiv 1 \pmod{10}$$

$$3^{33} \equiv 3^{4 \cdot 8+1} \equiv (3^4)^8 \cdot 3 \equiv 3 \pmod{10}$$

$(7,22)=1 , \phi(22)=\phi(2 \cdot 11)=22(1-\frac{1}{2})(1-\frac{1}{11})=10$

$\text{ So,from Euler's Theorem: } 7^{10} \equiv 1 \pmod{ 22 }$

$$7^{33} \equiv 7^{3 \cdot 10+3} \equiv (7^{10})^3 \cdot 7^3 \equiv 13 \pmod{22}$$

$$ \text{ We conclude that: } [c]_{10}=[3]_{10} \text{ and } [d]_{22}=[13]_{22} \Rightarrow c=3+10k, k \in \mathbb{Z} \text{ and } d=13+22l, l \in \mathbb{Z} \Rightarrow c=3, d=13$$

Therefore, $11c-5d=11 \cdot 3-5 \cdot 13=33-65=-32$

Could you tell me if it is right? (Thinking)(Thinking)

 

[I like Serena]

Hi! (Happy)

It is right! (Sun)

If you're interested, I have a little optimization for you.
You want to find out if $[7]_{22}$ has order $10$.
To do so, it suffices to verify $[7]_{22}^2$ and $[7]_{22}^5$.
If both are different from $1$, the order of $[7]_{22}$ is $10$. (Nerd)

 

[evinda]

Hi! (Happy)

It is right! (Sun)

If you're interested, I have a little optimization for you.
You want to find out if $[7]_{22}$ has order $10$.
To do so, it suffices to verify $[7]_{22}^2$ and $[7]_{22}^5$.
If both are different from $1$, the order of $[7]_{22}$ is $10$. (Nerd)

Why does it suffice to verify that $[7]_{22}^2$ and $[7]_{22}^5$ are different from $1$,in order to show that the order of $[7]_{22}$ is $10$? (Thinking)(Thinking)

 

[I like Serena]

Why does it suffice to verify that $[7]_{22}^2$ and $[7]_{22}^5$ are different from $1$,in order to show that the order of $[7]_{22}$ is $10$? (Thinking)(Thinking)

The order of $\mathbb Z_{22}$ is $\phi(22)=10$.
That means that the order of $[7]$ must divide $10$ (known as a consequence of Lagrange's theorem). (Wasntme)
If we can be sure that it isn't $2$ or $5$, it must be $10$.

 

[evinda]

The order of $\mathbb Z_{22}$ is $\phi(22)=10$.
That means that the order of $[7]$ must divide $10$ (known as a consequence of Lagrange's theorem). (Wasntme)
If we can be sure that it isn't $2$ or $5$, it must be $10$.

I understand...thank you very much! (Smile)