# some discrete mathematic question

1. The numbers $7$ and $23$ are relatively prime and therefore there must exist integers $a$ and $b$ such that $7a+23b=1$. Find such a pair of integers $(a,b)$ with the smallest possible $a>0$. Given this pair, can you determine the inverse of $7$ in $\mathbb{Z}_{23}$?

2. Solve the equation $3x+2=7$ in $\mathbb{Z}_{19}$.

3. Solve the equation $x^2+4x+1=0$ in $\mathbb{Z}_{23}$. Use the method described in Lecture $9.3$ using the quadratic formula.

4. What is the $11$th root of $2$ in $\mathbb{Z}_{19}$? (i.e. what is $2^{1/11}$ in $\mathbb{Z}_{19}$) Hint: observe that $11^{−1}=5$ in $\mathbb{Z}_{18}$.

5. What is the discete log of $5$ base $2$ in $\mathbb{Z}_{13}$? (i.e. what is $\log_2 5$) Recall that the powers of $2$ in $\mathbb{Z}_{13}$ are $\langle 2 \rangle = \{1,2,4,8,3,6,12,11,9,5,10,7\}$.

-
Interesting exercise! So what have you tried so far? –  azimut Mar 3 '13 at 22:30

$$(1)\;\;\;\;23=3\cdot 7+2\Longrightarrow 2=23-3\cdot 7\\\;\;\;\;\;\;\;7=3\cdot 2+1\Longrightarrow 1=7-3\cdot2$$
$$(2)\;\;\;\;\;3x+2=7\Longrightarrow 3x=7-2=7+17=5\pmod{19}\Longrightarrow x=5\cdot 3^{-1}\pmod{19}\\\text{but}\;\;\;3\cdot 13=2\cdot 19+1\ldots$$