(*
phi(modulus)=(p-1)*(q-1) must be coprime with e.
See: https://crypto.stackexchange.com/questions/12255/in-rsa-why-is-it-important-to-choose-e-so-that-it-is-coprime-to-%CF%86n
*)

e=3;

bits=4096;

While[True,
p=RandomPrime[{2^bits,2^(bits+1)}];
q=RandomPrime[{2^bits,2^(bits+1)}];
If[CoprimeQ[(p-1)*(q-1),e],Break[]]]

{p,q}

CoprimeQ[(p-1)*(q-1),e]