// A C++ program to check if a number is // Carmichael or not. #include    using namespace std; // utility function to find gcd of two numbers int gcd(int a int b) {  if (a < b)  return gcd(b a);  if (a % b == 0)  return b;  return gcd(b a % b); } // utility function to find pow(x y) under // given modulo mod int power(int x int y int mod) {  if (y == 0)  return 1;  int temp = power(x y / 2 mod) % mod;  temp = (temp * temp) % mod;  if (y % 2 == 1)  temp = (temp * x) % mod;  return temp; } // This function receives an integer n and // finds if it's a Carmichael number bool isCarmichaelNumber(int n) {  for (int b = 2; b < n; b++) {  // If 'b' is relatively prime to n  if (gcd(b n) == 1)  // And pow(b n-1)%n is not 1  // return false.  if (power(b n - 1 n) != 1)  return false;  }  return true; } // Driver function int main() {  cout << isCarmichaelNumber(500) << endl;  cout << isCarmichaelNumber(561) << endl;  cout << isCarmichaelNumber(1105) << endl;  return 0; } 

// JAVA program to check if a number is // Carmichael or not. import java.io.*; class GFG {  // utility function to find gcd of  // two numbers  static int gcd(int a int b)  {  if (a < b)  return gcd(b a);  if (a % b == 0)  return b;  return gcd(b a % b);  }  // utility function to find pow(x y)  // under given modulo mod  static int power(int x int y int mod)  {  if (y == 0)  return 1;  int temp = power(x y / 2 mod) % mod;  temp = (temp * temp) % mod;  if (y % 2 == 1)  temp = (temp * x) % mod;  return temp;  }  // This function receives an integer n and  // finds if it's a Carmichael number  static int isCarmichaelNumber(int n)  {  for (int b = 2; b < n; b++) {  // If 'b' is relatively prime to n  if (gcd(b n) == 1)  // And pow(b n-1)%n is not 1  // return false.  if (power(b n - 1 n) != 1)  return 0;  }  return 1;  }  // Driver function  public static void main(String args[])  {  System.out.println(isCarmichaelNumber(500));  System.out.println(isCarmichaelNumber(561));  System.out.println(isCarmichaelNumber(1105));  } } // This code is contributed by Nikita Tiwari. 

# A Python program to check if a number is # Carmichael or not. # utility function to find gcd of two numbers def gcd( a b) : if (a < b) : return gcd(b a) if (a % b == 0) : return b return gcd(b a % b) # utility function to find pow(x y) under # given modulo mod def power(x y mod) : if (y == 0) : return 1 temp = power(x y // 2 mod) % mod temp = (temp * temp) % mod if (y % 2 == 1) : temp = (temp * x) % mod return temp # This function receives an integer n and # finds if it's a Carmichael number def isCarmichaelNumber( n) : b = 2 while b<n : # If 'b' is relatively prime to n if (gcd(b n) == 1) : # And pow(b n-1)% n is not 1 # return false. if (power(b n - 1 n) != 1): return 0 b = b + 1 return 1 # Driver function print (isCarmichaelNumber(500)) print (isCarmichaelNumber(561)) print (isCarmichaelNumber(1105)) # This code is contributed by Nikita Tiwari. 

// C# program to check if a number is // Carmichael or not. using System; class GFG {  // utility function to find gcd of  // two numbers  static int gcd(int a int b)  {  if (a < b)  return gcd(b a);  if (a % b == 0)  return b;  return gcd(b a % b);  }  // utility function to find pow(x y)  // under given modulo mod  static int power(int x int y int mod)  {  if (y == 0)  return 1;  int temp = power(x y / 2 mod) % mod;  temp = (temp * temp) % mod;  if (y % 2 == 1)  temp = (temp * x) % mod;  return temp;  }  // This function receives an integer n and  // finds if it's a Carmichael number  static int isCarmichaelNumber(int n)  {  for (int b = 2; b < n; b++) {  // If 'b' is relatively prime to n  if (gcd(b n) == 1)  // And pow(b n-1)%n is not 1  // return false.  if (power(b n - 1 n) != 1)  return 0;  }  return 1;  }  // Driver function  public static void Main()  {  Console.WriteLine(isCarmichaelNumber(500));  Console.WriteLine(isCarmichaelNumber(561));  Console.WriteLine(isCarmichaelNumber(1105));  } } // This code is contributed by vt_m. 

 // PHP program to check if a // number is Carmichael or not. // utility function to find // gcd of two numbers function gcd($a $b) { if ($a < $b) return gcd($b $a); if ($a % $b == 0) return $b; return gcd($b $a % $b); } // utility function to find  // pow(x y) under given modulo mod function power($x $y $mod) { if ($y == 0) return 1; $temp = power($x $y / 2 $mod) % $mod; $temp = ($temp * $temp) % $mod; if ($y % 2 == 1) $temp = ($temp * $x) % $mod; return $temp; } // This function receives an integer // n and finds if it's a Carmichael // number function isCarmichaelNumber($n) { for ($b = 2; $b <= $n; $b++) { // If 'b' is relatively  // prime to n if (gcd($b $n) == 1) // And pow(b n - 1) % n  // is not 1 return false. if (power($b $n - 1 $n) != 1) return 0; } return 1; } // Driver Code echo isCarmichaelNumber(500) ' n'; echo isCarmichaelNumber(561) 'n'; echo isCarmichaelNumber(1105) 'n'; // This code is contributed by ajit ?> 

<script>  // Javascript program to check if a number is  // Carmichael or not.    // utility function to find gcd of  // two numbers  function gcd(a b)  {  if (a < b)  return gcd(b a);  if (a % b == 0)  return b;  return gcd(b a % b);  }    // utility function to find pow(x y)  // under given modulo mod  function power(x y mod)  {  if (y == 0)  return 1;    let temp = power(x parseInt(y / 2 10) mod) % mod;  temp = (temp * temp) % mod;    if (y % 2 == 1)  temp = (temp * x) % mod;    return temp;  }    // This function receives an integer n and  // finds if it's a Carmichael number  function isCarmichaelNumber(n)  {  for (let b = 2; b < n; b++) {  // If 'b' is relatively prime to n  if (gcd(b n) == 1)    // And pow(b n-1)%n is not 1  // return false.  if (power(b n - 1 n) != 1)  return 0;  }  return 1;  }    document.write(isCarmichaelNumber(500) + '
');  document.write(isCarmichaelNumber(561) + '
');  document.write(isCarmichaelNumber(1105)); </script> 

// C Program to find if a number is Carmichael Number #include int gcd(int a int b) //Function to find GCD { if (a<b) return gcd(b a); if (a % b == 0) return b; return gcd(b a % b); } // Function to find pow(xy) under given modulo mod int power(int x int y int mod)  { if (y == 0) return 1; int temp = power(x y / 2 mod) % mod; temp = (temp * temp) % mod; if (y % 2 == 1) temp = (temp * x) % mod; return temp; } //Function to find if received number n is a Carmichael number int carmichaelnumber(int n)  { for (int b=2;b<n;b++)  { if (gcd(bn)==1) if (power(bn-1n)!= 1) { printf('0'); return 0; } } printf('1'); return 0; }; int main() { carmichaelnumber(500); printf('n'); carmichaelnumber(561); printf('n'); carmichaelnumber(1105); return 0;   // This code is contributed by Susobhan Akhuli }