I have to replicate the key set up process of RSA public encryption algorithm.
Basically I am given two random primes, $P = 7$ and $Q = 5$.
I calculate the following
$N = 5 \cdot 7 = 35$
$O(N) = (p-1)(q-1) = 4\cdot6 = 24$
$e = 7$ -> this is the encryption key
To find the decryption key I need to solve the following equation:
$e*d \equiv 1$ (mod $n$) where $0 \le d \le n$.
I have watched YouTube videos where they explain how to calculate the modular inverse using Euclid's Algorithm, but after the first step I end up with:
$35 = 5(7) + 0$
In all the videos I saw, they usually end up with a remainder of $1$ so that they then set the equation to be equal to 1 and then they substitute to calculate the inverse modulo, but I just end up with
$35 = 5(7) + 0$
and I don't know how to proceed.
There is a multiplicative inverse of $d$ mod $n$ only when $\gcd(d,n)=1$.
In particular, $\gcd(7,35)=7>1$, so there is no inverse of $7$ modulo $35$.
You won't find $d$ such that $7d\equiv1 \bmod 35$.
If there were, then we'd have $35$ dividing $7d-1$,
so $7$ dividing $7d-1$, so $7$ dividing $1$, which is clearly absurd.
See this Wikipedia page for further information.