def gcd(a,b):
  if(b==0):
    return a
  else:
    return gcd(b,a%b)
p=int (input("enter first prime number"))
q=int (input("enter second prime number"))
m=int (input("enter the message"))
n=p*q
fn=(p-1)*(q-1)
e=2
while(e<fn):
  if(gcd(e,fn)==1):
    break
  else:
    e+=1
d=1
while(d>0):
  if(d*e)%fn==1:
    break
  else:
    d+=1
c=(m**e)%n
p=(c**d)%n
print("encrypted message is:",c)
print("decrypted message is:",p)