# Values of p and q when e = 3 (RSA)?

I am doing a paper on textbook RSA (this is for high school btw) and in my example I need two very large primes, but I want my $e = 3$.

Is there a short way to calculate the values of $p$ and $q$ such that $gcd(e, φ(pq)) = 1$?

• Sample primes at random until you find two (p, q) such that 3 divides neither (p-1) nor (q-1). – puzzlepalace Oct 14 '15 at 22:37
• Do you need to know how to find large primes, or just how to find large primes with that property? – Seth Oct 15 '15 at 2:02
• puzzlepalace's hint can be rewritten as "test only numbers that are 2 mod 3 for primeness". – j.p. Oct 15 '15 at 8:31