A problem in Number Theory?

Question

Let p,q are two primes s.t p So there is a number b s.t ab=1(mod(phi(n))).Prove gcd(b,n)=1.phi is Euler phi function

Answer 1

If you assume that gcd(a,phi(n))=1, then the existence of b such that ab=1(mod(phi(n))) is immediate (b is an inverse of a mod phi(n)), because:

gcd(a,phi(n))=1 <=> there are integers x,y such that
ax+phi(n)y=1
(if gcd(m,n)=d, then there are integers x,y such that d=mx+ny)

<=> ax-1=yphi(n) <=> ax=1mod(phi(n))

And x can be computed efficiently using the Extended Euclidean algorithm.

The additional hypothesis are not needed for this particular question, but they appear in the context of RSA-type problems (RSA is a common public-key cryptosystem), and I suspect that your question came from the study of the correctness of this system. In this context a will be the secret private key, and the computed b the non-secret public key.

Answer 2

As a grad pupil, you in all probability understand those already yet, purely in case you nevertheless have not heard concerning to the Milenium issues contest, right here they bypass: * Birch and Swinnerton-Dyer Conjecture * Hodge Conjecture * Navier-Stokes Equations * P vs NP * Poincaré Conjecture * Riemann hypothesis * Yang-turbines concept i think the Poincaré Conjecture has been solved this twelve months, although. playstation : good success. :-)