2

Show that $\gcd(n,\theta)=1$, and find the inverse $s$ of $n$ modulo $\theta$ satisfying $0 < s < \theta$ for $n=7$ and $\theta=20$.

user47805
  • 376
Chandler K Sharp
  • 39
  • 4
    I'm voting to close this question as off-topic because it's old, simple, and won't help anyone in the future. Next, it should be deleted. – Lord_Farin Jun 08 '16 at 16:12

2 Answers2

0

You are looking for a number $s \in \{1,...,19 \}$ such that $s \cdot 7 = 1 \mod 20$.

One way is to just check all $19$ numbers.

Alternativley:

Since $7$ is prime, it follows that $\gcd(7,20) = 1$. We can also see that $3\cdot 7 - 1 \cdot 20 = 1$ (this is Bézout's identity). Hence $3\cdot 7 = 1 \mod 20$. It follows that $3$ is the inverse of $7$.

copper.hat
  • 172,524
0

By the Euclidean Algorithm,

$20=2\cdot 7+6$

$7=1\cdot6+1$

So $(20,7)=1$. Now we can also say that $7-6=1$ and $20-2\cdot7=6$. Substituting gives $1=7-(20-2\cdot7)$ simplifying, $1=7+2\cdot7-20$ and $1=3\cdot7-20$. So $7^{-1}=3\pmod {20}$.

This was a bit needlessly complicated but it illustrates the Euclidean Algorithm and how to write $(a,b)$ as a linear combination of $a$ and $b$.

user47805
  • 376