Números primos en matemáticas discretas

Descripción general:
un número entero p>1 se llama número primo , o primo si los únicos divisores positivos de p son 1 y p. Un entero q>1 que no es primo se llama compuesto.

Ejemplo:
los números enteros 2,3,5,7 y 11 son números primos y los números enteros 4,6,8 y 9 son compuestos.

Teorema-1: 
Un entero p>1 es primo si y solo si para todos los enteros ayb, p divide ab implica que p divide a o p divide a b.

Ejemplo: 
considere el número entero 12. Ahora 12 divide 120 = 30 x 4 pero 12|30 y 12|4. Por lo tanto, 12 no es primo.

Teorema-2: 
Todo número entero n>=2 tiene un factor primo.

Teorema-3: 
Si n es un número entero compuesto, entonces n tiene un factor primo que no excede √n.

Ejemplo-1:
¿Determina cuáles de los siguientes números enteros son primos?

a) 293 b) 9823

Solución –

1. Primero encontramos todos los primos p tales que p ² < = 293. Estos primos son 2, 3, 5, 7, 11, 13 y 17. Ahora, ninguno de estos primos divide a 293. Por lo tanto, 293 es un primo.
2. Consideramos primos p tales que p2< = 9823. Estos primos son 2,3,5,7,11,13,17, etc. Ninguno de 2,3,5,7 puede dividir a 9823. Sin embargo, 11 divide a 9823. Por lo tanto , 9823 no es un número primo.

Ejemplo-2: 
Sea n un entero positivo tal que n ² -1 es primo. Entonces n =?

Solución – 
Podemos escribir, n ² -1 = (n-1)(n ² +n+1). Como n ³ -1 es primo, n-1 = 1 o n ² +n+1 = 1. Ahora n>=1, entonces n ² +n+1 > 1, es decir, n ² +n+1 != 1. Por tanto, debemos tener n-1 = 1. Esto implica que n=2.

Ejemplo-3:
Sea p un número primo tal que mcd(a, p ³ )=p y mcd(b,p ⁴ )=p. Encuentre mcd(ab,p ⁷ ).

Solución – 
Por la condición dada, mcd(a,p ³ )=p. Por lo tanto, p | una. Además, p ² |a.(Porque si p ² | a, entonces mcd (a,p ³ )>=p ² >p, lo cual es una contradicción.) Ahora a puede escribirse como un producto de potencias primas. Porque p|ayp ² | a, se sigue que p aparece como factor en la factorización prima de a, pero p ^k , donde k>=2, no aparece en esa factorización prima. De manera similar, mcd(b,p ⁴ )=p implica que p|b y p ² |b. Como antes, se sigue que p aparece como un factor en la descomposición en factores primos de a, pero p ^k , donde k>=2, no aparece en esa descomposición en factores primos. Ahora se sigue que p² |ab yp ³ |ab. Por lo tanto, mcd(b,p ⁷ ) = p ² .

Algoritmo de prueba de primalidad:

for i: [2,N-1]
  if i divides N
     return "Composite"
     
return "Prime"        

Ejemplo –
Tomemos un ejemplo y hace que el algoritmo sea más eficiente, 36=

Take the inputs of a and b until,    
 a<=b
                                                                
 a . b = N
 a . N/a = N

Algoritmo modificado:

for i : [2,√n]
   if i divides N
     return "Composite"
     
return "Prime"    

// C++ program to check primality of a number
#include <bits/stdc++.h>
using namespace std;
 
bool is_prime(int n){
   for(int i = 2; i * i <= n; i++){
     if(n % i == 0){
       return false;
       //if the number is composite or not prime.
     }
   }
  return true;
    // number is prime.
}
int main() {
 
    int n;
    cin >> n;
    cout << is_prime(n) ? "prime" : "composite";
    return 0;
}

// Java program to check primality of a number
 
/*package whatever //do not write package name here */
 
import java.util.*;
class prime{
    public Boolean is_prime(int n){
        for(int i = 2; i * i <= n; i++){
            if(n % i == 0){
                return false;
              //if the number is composite or not prime.
            }
        }
        return true;
      // number is prime.
    }
 
}
 
class GFG {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        prime ob = new prime();
        System.out.println(ob.is_prime(n) ? "Prime" : "Composite");
    }
}

# Python program to check primality of a number
import math
 
 
def is_prime(n):
    for i in range(2, int(math.sqrt(n))):
        if(n % i == 0):
            return False
        # if the number is composite or not prime.
 
    return True
    #  number is prime.
 
 
if __name__ == "__main__":
 
    n = int(input())
    if is_prime(n):
        print("prime")
    else:
        print("composite")
 
    # This code is contributed by rakeshsahni

<script>
// JavaScript program to check primality of a number
function is_prime(n)
{
   for(var i = 2; i * i <= n; i++)
   {
     if(n % i == 0){
       return false;
        
       // if the number is composite or not prime.
     }
   }
  return true;
    // number is prime.
}
    var n;
    document.write(is_prime(n) ? "prime" : "composite");
     
// This code is contributed by shivanisinghss2110
</script>

Algoritmo para encontrar números primos:
En matemáticas, la criba de Eratóstenes es un antiguo algoritmo para encontrar todos los números primos hasta cualquier límite dado.

Algorithm Sieve of Eratosthenes is input: an integer n > 1.
output : all prime numbers from 2 through n.

let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
    
    for i = 2, 3, 4, ..., not exceeding √n do
        if A[i] is true
            for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
                A[j] := false

    return all i such that A[i] is true.