RSA encryption/decryption process is not working correctly I'm trying to apply the RSA cryptosystem to encrypt a byte M=72, using predefined modulus n, public key exponent e and private key d.

(n, e, d, p, q) = (4802, 5, 59, 43, 8)

In order to accomplish that, I used the following code on Python console:

C=(M**e)%n
M=(C**d)%n
print M



the first instruction encrypts the byte as C: using the RSA encryption mathematical expression (** stands for exponentional, and % for modulus in Python programming language)
the second decrypts C to get M back: using the RSA decryption mathematical expression.


However, the output shows:


  2816


which means that M was incorrectly computed as '2816', although I'm pretty sure that all the values of n, e, d, p and q respect the RSA public key algorithm specification.

Does anyone have any idea?
The RSA definition requires $n = p q$ where $p$ and $q$ are distinct primes.
In your example $n=4802$ has a factorization as;
$$ n = 2 \cdot 7^4$$ with 10 divisors. Also, your $q=8$ is not a prime.

Here a working example for you with  fips.186-4 standard, or see $\lambda$ versus $\varphi$ in RSA;

Select two distinct random primes;  $p = 47, q = 43$
compute $n = 47*43 = 2021 $
compute $\lambda(n)=\operatorname{lcm}(p-1,q-1)= \operatorname{lcm}(62,42)= 966$
select $e$;

$e=3$;
$gcd(3,966) = 3 \neq 1$ chose another;
$e=5$
check $gcd(5,966) = 1$, ok.


$d = 773$ by $d = e^{-1} \bmod{\lambda(n)}$

As noted by Fgrieu on the comments, make sure that you are using efficient methods. For example;

For finding prime numbers probabilistic Miller–Rabin primality test, should be enough. Note that Miller–Rabin primality test is probabilistic; composite output is always true, prime output has probability defined by the number iterations.
For modular multiplication there are various chocies as  $2^k$-ary sliding window algorithm used by GNU GMP, left-to-right or right-to-left modular multiplications.
Modular inverse by the extended-gcd algorithm.


Calculating with Wolfram Alpha
One can use the highlighted text to enter at WolframAlpha with your paramaters:

$\lambda(n):$   CarmichaelLambda(2021) result is 966
$gcd(5,966):$   gcd(5,966) result is 1
$d:$            5^-1 mod CarmichaelLambda(2021) result is 773
encrypt $m=65:$ 65^5 mod 2021 result is c=168
decrypt $c=168:$ 168^773 mod 2021 result is 65

Note: if you are using textbook RSA then change CarmichaelLambda() with phi()