I understand that the Euclidean Algorithm can be used as the pen and paper method to find the gcd of two numbers. However, I am studying the RSA algorithm and in this algorithm I need to find a number $e$ such that $\gcd(n,e) = 1$ where $n = 3120$ in this case, also $1 < e < n$. Is there some way the Euclidean Algorithm can be rearranged to solve this problem (pen and paper method)?
[Math] Given one number find a second number such that the gcd of both numbers is 1
elementary-number-theory
Best Answer
Find the prime factorization of $n$. In general this is hard, but for $n=3120$ it's easy, because $3120$ is quite small, and also so smooth; you don't even need paper and pencil: $$3120 = 2^4\cdot 3\cdot 5\cdot 13.$$
Now any number $e$ that is not divisible by $2,3, 5,$ or $13$ will have $\gcd(3120, e) = 1$. To find one, take zero or more of primes that are not $2,3, 5,$ or $13$ and multiply them. For example, $7, 7, 11, $ and $23$:
$$7^2\cdot11\cdot 23 = 12397$$
and $\gcd(3120,12397) = 1$.
Every such number $e$ can be found in this way.