# Check if a number is Euler Pseudoprime in Python

Hello coders, in this tutorial we are going to check whether a given number is Euler Pseudoprime or not in Python. Before we proceed firstly we will discuss what is Euler Pseudoprime number, So let’s start.

## What is Euler Pseudoprime?

A number n is said to be Euler Pseudoprime to base b  when it follows the condition:

1.  The base of the number is greater than 0(zero) and  the number n should be a composite number
2. ( b^((n-1)/2)))%n is equal to n or n-1
3. b and n should be coprime numbers.

For example

```n=121 and b=3
then the number is Euler Pseudoprime```

Now The Python code for implementation of the above concept:-

```def isComposite(n) :
for i in range(2, int(sqrt(n)) + 1) :
if (n % i == 0) :
return True;
return False;
def Power(x, y, p) :
res = 1;
x = x % p;
while (y > 0) :
if (y & 1) :
res = (res * x) % p;
y = y >> 1; # y = y/2
x = (x * x) % p;
return res;
def isEulerPseudoprime(N, A) :
if (A <= 0) :
return False;
if (N % 2 == 0 or not isComposite(N)) :
return False;
if (gcd(A, N) != 1) :
return false;
mod = Power(A, (N - 1) // 2, N);
if (mod != 1 and mod != N - 1) :
return False;
return True;
if __name__ == "__main__" :
N = 121; A = 3;
if (isEulerPseudoprime(N, A)) :
print("Yes");
else :
print("No");

```

Output:-

`Yes`