Finding modular inverse of $q$ modulo $p$, where $q,r$ are prime numbers

Question

I have to write a small program with the following instructions:

Given are p and q with p and q different prime numbers. Write a small program that calulates the following values: 1) Determine a solution z for qz ≡ 1 mod p ...

My question is: As p and q have to be prime numbers (do I get this right?), the solution for z is always 1, right? As z should be the gcd and the gcd of prime numbers is always 1?

Thank you very much.

Update: Ok, I was completely wrong. I have no clue where to start with the problem. So I can solve it with the extended euklidean algorithm?

Let's give that bold hypothesis a try: If $p=17$ and $q=11$, do you think that $11\cdot 1\equiv 1\pmod{17}$? — Hagen von Eitzen, Nov 10 '13 at 14:27
Chinese Remainder Thoerem is used to "glue" two congruence together, in this case you have only on congurence relation and you are interested in the modular inverse of q modulo p — Stefan4024, Nov 10 '13 at 14:31

score 2 · Answer 1 · answered Nov 10 '13 at 14:35

2

Actually you are interested in finding the modular inverse of $q$ modulo $p$. You can do that using the Extended Euclidean Algorithm. Note that:

$$qz \equiv 1 \pmod p \iff qz + pk = 1$$

for some whole number $k$. Do you know how to continue to solve this linear Diophantene Equation?

answered Nov 10 '13 at 14:35

Stefan4024

35,843

Thank you! I don't know how to solve this. Can you give me a hint? – Munis Nov 10 '13 at 19:03
The Linear Diphantene Solution is solved using the Extended Eucledan Algorithm for more detailed explanation of the algorithm look here – Stefan4024 Nov 10 '13 at 22:43
Thank you! I was able to solve it :) – Munis Nov 11 '13 at 13:40

Finding modular inverse of $q$ modulo $p$, where $q,r$ are prime numbers

1 Answers1