Números de Carmichael

Se dice que un número n es un número de Carmichael si satisface la siguiente condición aritmética modular: 
 

  power(b, n-1) MOD n = 1, 
  for all b ranging from 1 to n such that b and 
  n are relatively prime, i.e, gcd(b, n) = 1 

Dado un entero positivo n, encuentre si es un número de Carmichael. Estos números tienen importancia en el Método Fermat para las pruebas de primalidad .
Ejemplos: 
 

Input :  n = 8
Output : false
Explanation : 8 is not a Carmichael number because 3 is 
              relatively prime to 8 and (38-1) % 8
              = 2187 % 8 is not 1.
              
Input :  n = 561
Output : true

La idea es simple, iteramos a través de todos los números del 1 al n y para cada número relativamente primo, verificamos si su potencia (n-1) en el módulo n es 1 o no. 
A continuación se muestra un programa para verificar si un número dado es Carmichael o no. 
 

// A C++ program to check if a number is
// Carmichael or not.
#include <iostream>
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
// 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) + "</br>");
    document.write(isCarmichaelNumber(561) + "</br>");
    document.write(isCarmichaelNumber(1105));
 
</script>

// C Program to find if a number is Carmichael Number
#include<stdio.h>
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(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;
}
 
 
//Function to find if received number n is a Carmichael number
int carmichaelnumber(int n)   
{
for (int b=2;b<n;b++)
{
if (gcd(b,n)==1)
if (power(b,n-1,n)!= 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
 
}

Producción: 

0
1
1

Este artículo es una contribución de Ashutosh Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.