computer science studies - residue class rings.
I have to calculate the following expression in $ \mathbb{Z_9}$
and the other one in $ \mathbb{Z_{16}}$
my question is how one should handle $-1, 23, 10$ in the "powers"?
are they really powers or do they have another meaning perhaps?
Thank you for your help
Here we show the OP some techniques (tricks?) for finding the inverse elements in $\mathbb{Z_{16}}$.
Since $15 \equiv -1 \pmod{16}$ we can factor $15$ and write
$\quad 3\cdot 5 \equiv -1 \pmod{16} \; \text{ iff } \; (-3) \cdot 5 \equiv 1 \pmod{16} \; \text{ iff } \; 5 \cdot 13 \equiv 1 \pmod{16}$
and
$\quad 3\cdot 5 \equiv -1 \pmod{16} \; \text{ iff } \; 3 \cdot (-5) \equiv 1 \pmod{16} \; \text{ iff } \; 3 \cdot 11 \equiv 1 \pmod{16}$
A good start - we've found the inverse of four residue primes. By working with our 'material', we'll find $[7]^{-1}$ by multiplying $[7]$ with known quantities and see if we transform it to $[1]$.
$\quad 7 \cdot 3 \equiv 21 \pmod{16}$
$\quad 7 \cdot 3 \equiv 5 \pmod{16}$
$\quad 7 \cdot 3 \cdot 13 \equiv 5 \cdot 13 \pmod{16}$
$\quad 7 \cdot (39) \equiv 1 \pmod{16}$
$\quad 7 \cdot 7 \equiv 1 \pmod{16}$
So $[7]^{-1} = 7$.
Here are the remaining invertible elements,
$\quad \large [9]^{-1} = \bigr([3]^{2}\bigr)^{-1} = \bigr([3]^{-1}\bigr)^2 = [11^2] = [121] = [9]$
$\quad \large [15]^{-1} = [3\cdot5]^{-1} = [3^{-1} \cdot 5^{-1}] = [11 \cdot 13] = [15]$
(there is an easier way to find $[15]^{-1}$)
$\quad \large [1]^{-1} = [1]$
So $\mathbb{Z_{16}}$ has $8 = \phi(16)$ invertible elements.
In a ring, $x^n$ means the power. So you have, for instance, $x=[5]_9$ as an element of $\mathbb{Z}/9\mathbb{Z}$ and you raise it to the power $10$.
What can you do here? You know that $\gcd(5,9)=1$ and therefore Euler-Fermat applies, yielding $$ 5^{\varphi(9)}=5^6\equiv1\pmod{9} $$ Therefore $$ [5]_9^{10}=[5_9]^6[5]_9^4=[5]_9^4=([5]_9^2)^2)=[7]_9^2=[4]_9 $$ What about $[7]_{16}^{-1}$? Hint: $7\cdot7=49$.
