Do You Remember Inverses?
What is 5 − 1 ( m o d 1 7 ) ?
Hint: Remember that inverses multiply to 1.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
Its not clear. can u elaborate it. thank you..
Log in to reply
The multiplicative inverse of 5 modulo 17 is a number 5 − 1 ∈ { 0 , 1 , … , 1 6 } such that 5 ⋅ 5 − 1 leaves a remainder of 1 when divided by 17.
You can check that 5 × 7 = 3 5 = 1 7 × 2 + 1 , so 7 is a multiplicative inverse of 5 modulo 17.
For more information, check out Modular Arithmetic - Multiplicative Inverses .
If b and m are relatively prime, then Euler's totient theorem states that b ϕ ( m ) = 1 ( m o d m ) , w h e r e ϕ ( m ) is the totient function.
it follows that b − 1 = b ϕ ( m ) − 1 ( m o d m ) . (see wiki)
for any prime number ϕ ( m ) = m − 1
plug in the numbers b = 5 , 1 7 = m , ϕ ( m ) = 1 6 = > b − 1 = 7
You can write 5^-1 as 1/5=(-16)/5=-3-1/5 t. I. 2/5=-3=14 then 1/5=7 (mod. 17)
g c d ( a , b ) = u ∗ a + v ∗ b
| r | q | u | v |
| 17 | / | 1 | 0 |
| 5 | / | 0 | 1 |
| 2 | 3 | 1 | -3 |
| 1 | 2 | -2 | 7 |
so g c d ( 5 , 1 7 ) = 1 = u ∗ 1 7 + v ∗ 5 = − 2 ∗ 1 7 + 7 ∗ 5
1 ≡ − 2 ∗ 1 7 + 7 ∗ 5 ( mod 1 7 ) (factor of 17 will cancel out with mod 17)
1 ≡ 7 ∗ 5 ( mod 1 7 )
5 − 1 ≡ 7 ( mod 1 7 )
We have 5 × 7 = 3 5 ≡ 1 ( m o d 1 7 ) , so 5 − 1 ≡ 7 ( m o d 1 7 ) .