# Check if a number is Euler Pseudoprime in Java

In this article, we are going to see and understand how to check if a number is Euler Pseudoprime or not in Java.

Definition:-  An integer ‘N’ is called Euler Pseudoprime to the base B if they satisfy the following conditions –

1.  B > 0
2. N is an odd composite number.
3. B and N are co-prime i.e. GCD(B, N) = 1
4. (B(N – 1) / 2 ) % N is either 1 or N – 1.

Example:-

1. N = 341 , B = 4

Here, as B>0 and N is an odd composite number, B and N are co-prime and (4(341 – 1) / 2 ) % 341 = 1

Therefore it is an Euler Pseudoprime number.

2. N =341, B = 3

Here, as B>0 and N is an odd composite number, B and N are co-prime but (3(341 – 1) / 2 ) % 341 = 67

Therefore it is not an Euler Pseudoprime number.

The code below will check if a number is Euler Pseudoprime in Java.

```class Euler
{

// Function to Check if two numbers are coprime or not
public boolean check_coprime(int b,int n)
{
// get gcd result of b and n
int result = gcd(b,n);

// if result is not 1 then it is not coprime
if(result != 1)
return false;
return true;
}

// Function to Check gcd of the numbers
public int gcd(int x, int y)
{
if(x==0)
return y;
if (y==0)
return x;
if (x==y)
return x;
if (x>y)
return gcd(x-y,y);
return gcd(x,y-x);
}

// Function to Check if the given number n is an odd composite number or not
public boolean check_ifOddcomposite(int n)
{
for(int k=2;k<= n/2;k++)
{
// if it is divisible by any number less then n/2
// and if it is odd number then it is odd composite number
if (n%k == 0 && n%2 == 1)
return true;
}
return false;
}

// Function to calculate result of (A ^ P) % N
public int calc_Result(int A, int P, int N)
{
int result = 1;
// Update value of 'A' if it is greater than or equal to 'N'
A = A%N;
while(P>0)
{
// If 'P' is odd, multiply 'A' with result
if(P % 2 == 1)
{
result = (result*A) % N;
}
P = P/2;
A = (A * A) % N;
}
return result;
}

// Function to check if the Number is a Euler Pseudoprime number or not
public void check_EulerPseudoprimeNo(int N, int B)
{
// Checking all the conditions
// Check if base is valid
if(B >= 0){
// Check if N is a odd composite number
if(check_ifOddcomposite(N)){
// Check if B and N are coprime
if(check_coprime(B,N)){
// Calculate result of (B ^ (N – 1)/2 ) % N and store in 'res' variable
int res = calc_Result(B, (N-1)/2 , N);

// Check if the result is either 1 or N-1
if (res == 1 || res == N - 1){
// All the conditions for Euler Pseudoprime are satisfied
System.out.println("It is a Euler Pseudoprime Number");
return;
}
}
}
}
// If any condition fails
System.out.println("Not a Euler Pseudoprime Number");
}
}

class Main{

public static void main(String args[])
{
int N,B;
N=121;
B=3;

// Creating object of Euler class
Euler obj=new Euler();

// Calling funtion check_EulerPseudoprimeNo
obj.check_EulerPseudoprimeNo(N,B);

}
}```

In the above code, first, we are defining important functions like check_coprime(), gcd(), and check_ifOddcomposite() to check for our first two conditions of Euler Psuedoprime. Then, to check for the third condition, we define calc_result and then to check if all conditions satisfy and whether it is an Euler Psuedoprime or not, we define check_EulerPseudoprimeNo().

As a result, the following output is generated:-

```C:\Users\KIRA\Desktop\case study>javac Main.java

C:\Users\KIRA\Desktop\case study>java Main
It is a Euler Pseudoprime Number```

I hope you like the article, feel free to comment down your queries.