Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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\}$.

share|improve this question
6  
Interesting exercise! So what have you tried so far? –  azimut Mar 3 '13 at 22:30

1 Answer 1

Hints:

$$(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$$

Well, try to do something with this and, if still stuck, write back, show your work and where you're having problems.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.