Teoría de Números | Generadores de grupo cíclico finito bajo adición

Dado un número n, encuentre todos los generadores del grupo aditivo cíclico bajo el módulo n. Generador de un conjunto {0, 1, … n-1} es un elemento x tal que x es menor que n, y usando x (y la operación de suma), podemos generar todos los elementos del conjunto.
Ejemplos: 
 

Input : 10
Output : 1 3 7 9
The set to be generated is {0, 1, .. 9}
By adding 1, single or more times, we 
can create all elements from 0 to 9.
Similarly using 3, we can generate all
elements.
30 % 10 = 0, 21 % 10 = 1, 12 % 10 = 2, ...
Same is true for 7 and 9.

Input  : 24
Output : 1 5 7 11 13 17 19 23

Una solución simple es ejecutar un ciclo de 1 a n-1 y para cada elemento verificar si es generador. Para verificar el generador, seguimos agregando elementos y verificamos si podemos generar todos los números hasta que el resto comience a repetirse.
Una solución Eficiente se basa en el hecho de que un número x es generador si x es primo relativo de n, es decir, mcd(n, x) =1.
A continuación se muestra la implementación del enfoque anterior:
 

// A simple C++ program to find all generators
#include <bits/stdc++.h>
using namespace std;
 
// Function to return gcd of a and b
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b%a, a);
}
 
// Print generators of n
int printGenerators(unsigned int n)
{
    // 1 is always a generator
    cout << "1 ";
 
    for (int i=2; i < n; i++)
 
        // A number x is generator of GCD is 1
        if (gcd(i, n) == 1)
            cout << i << " ";
}
 
// Driver program to test above function
int main()
{
    int n = 10;
    printGenerators(n);
    return 0;
}

// A simple Java program to find all generators
 
class GFG {
     
 
// Function to return gcd of a and b
static int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b%a, a);
}
 
// Print generators of n
static void printGenerators(int n)
{
    // 1 is always a generator
    System.out.println("1 ");
 
    for (int i=2; i < n; i++)
 
        // A number x is generator of GCD is 1
        if (gcd(i, n) == 1)
            System.out.println(i +" ");
}
 
// Driver program to test above function
public static void main(String args[])
{
    int n = 10;
    printGenerators(n);
}
}

# Python3 program to find all generators
 
# Function to return gcd of a and b
def gcd(a, b):
    if (a == 0):
        return b;
    return gcd(b % a, a);
 
# Print generators of n
def printGenerators(n):
     
    # 1 is always a generator
    print("1", end = " ");
 
    for i in range(2, n):
 
        # A number x is generator
        # of GCD is 1
        if (gcd(i, n) == 1):
            print(i, end = " ");
 
# Driver Code
n = 10;
printGenerators(n);
     
# This code is contributed by mits

// A simple C# program to find all generators
using System;
 
class GFG
{
     
// Function to return gcd of a and b
static int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
 
// Print generators of n
static void printGenerators(int n)
{
    // 1 is always a generator
    Console.Write("1 ");
 
    for (int i = 2; i < n; i++)
 
        // A number x is generator of GCD is 1
        if (gcd(i, n) == 1)
            Console.Write(i +" ");
}
 
// Driver code
public static void Main(String []args)
{
    int n = 10;
    printGenerators(n);
}
}
 
// This code contributed by Rajput-Ji

<?php
// PHP program to find all generators
 
// Function to return gcd of a and b
 
function gcd($a, $b)
{
    if ($a == 0)
        return $b;
    return gcd($b % $a, $a);
}
 
// Print generators of n
function printGenerators($n)
{
     
    // 1 is always a generator
    echo "1 ";
 
    for ($i = 2; $i < $n; $i++)
 
        // A number x is generator
        // of GCD is 1
        if (gcd($i, $n) == 1)
            echo $i, " ";
}
 
// Driver program to test
// above function
    $n = 10;
    printGenerators($n);
     
// This code is contributed by Ajit
?>

<script>
 
// A simple Javascript program to
// find all generators
 
// Function to return gcd of a and b
function gcd(a, b)
{
    if (a == 0)
        return b;
         
    return gcd(b % a, a);
}
 
// Print generators of n
function printGenerators(n)
{
     
    // 1 is always a generator
    document.write("1 ");
 
    for(var i = 2; i < n; i++)
 
        // A number x is generator of
        // GCD is 1
        if (gcd(i, n) == 1)
            document.write(i + " ");
}
 
// Driver Code
var n = 10;
 
printGenerators(n);
 
// This code is contributed by Kirti
 
</script>

Producción : 

1 3 7 9

¿Como funciona esto?  
Si consideramos todos los restos de n múltiplos consecutivos de x, entonces algunos restos se repetirían si MCD de x y n no es 1. Si algunos restos se repiten, entonces x no puede ser un generador. Tenga en cuenta que después de n múltiplos consecutivos, los residuos se repetirán de todos modos.
Observación interesante: 
el número de generadores de un número n es igual a Φ(n) donde Φ es la función Euler Totient .
Este artículo es una contribución de Ujjwal Goyal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@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.