Comprobador seudoprimo Euler-Jacobi
El 561 es un seudoprimo de Euler–Jacobi en base 2: la potencia con exponente 280 deja resto 1, igual que su símbolo de Jacobi, aunque 561 es compuesto. Escriba un compuesto impar y una base para ver cada valor del veredicto. Gratis en su navegador.
- Gratis
- Funciona en su navegador
- Sin registro
- Sus datos no salen de su equipo
Ejecutar — gratis
Ejemplo resuelto
- N
- 561
- A
- 2
- Gcd
- 1
- Símbolo de Jacobi
- 1
- Exponente
- 280
- Resto
- 1
Un seudoprimo de Euler–Jacobi respecto de una base dada es un entero compuesto impar que cumple el criterio de Euler como si fuera primo. Para una base a coprima, eso significa que a elevado a (n menos uno) entre dos es congruente con el símbolo de Jacobi de a sobre n, módulo n. Todo primo impar que no divide a satisface la misma congruencia, de modo que los compuestos que aún pasan son los fallos interesantes de una prueba al estilo Solovay–Strassen. Este comprobador responde exactamente a esa pregunta: dados n compuesto impar y la base a, decide si n es seudoprimo de Euler–Jacobi en esa base. La respuesta informa el gcd, el símbolo de Jacobi, la potencia modular, si la congruencia se cumple y un booleano verdadero solo cuando se satisface la definición completa.
Qué es un seudoprimo de Euler–Jacobi y en qué se diferencia de Fermat y Euler
El criterio de Euler afirma que si p es un primo impar y a no es divisible por p, entonces a elevado a (p menos uno) entre dos es congruente con el símbolo de Legendre de a sobre p, módulo p. El símbolo de Jacobi (a/n) extiende ese carácter cuadrático de los primos impares a cualquier entero positivo impar n, así que resulta tentador escribir la misma congruencia con n en lugar de p. Cuando n es un primo impar ambos símbolos coinciden y la congruencia es un teorema.
Cuando n es impar y compuesto, la congruencia aún puede valer para algunas bases aunque n no sea primo. Esos n se llaman seudoprimos de Euler–Jacobi en base a, siempre que gcd(a, n) valga uno. La condición es estrictamente más fuerte que la prueba de Fermat (a elevado a n menos uno congruente con uno módulo n) y también más fuerte que la prueba de Euler débil, que solo pide que la potencia modular sea más uno o menos uno.
El ejemplo clásico es trescientos cuarenta y uno en base dos: es seudoprimo de Fermat, dos elevado a ciento setenta vale uno módulo trescientos cuarenta y uno, pero el símbolo de Jacobi (2/341) es menos uno, de modo que la congruencia de Euler–Jacobi falla. Quinientos sesenta y uno, el menor número de Carmichael, sí cumple la congruencia en base dos y por tanto es seudoprimo de Euler–Jacobi en esa base. Noventa y uno en base diez es otro ejemplo de aula que este comprobador confirma.
Contrato de entrada, campos de respuesta y comportamiento ante errores
Si n es menor que nueve, par o primo, el manejador rechaza la petición: los seudoprimos de Euler–Jacobi son compuestos impares por definición, y tratar un primo como seudoprimo fallido enseñaría la lección equivocada. Esos fallos de validación no se facturan. La cadena criterion reitera a^((n-1)/2) ≡ (a/n) (mod n) para que una página o cuaderno muestre la definición junto al veredicto.
Cuando gcd es mayor que uno, Jacobi vale cero y el par no es de Euler–Jacobi aunque alguna potencia accidental se anule. Ejemplo: n igual a quinientos sesenta y uno y a igual a dos produce jacobi uno, remainder uno y una marca verdadera; n igual a trescientos cuarenta y uno y a igual a dos produce jacobi menos uno, remainder uno y una marca falsa. Toda la aritmética es BigInt exacto; no hay punto flotante ni testigo aleatorio.
Dónde resulta útil un comprobador de seudoprimos de Euler–Jacobi
Los cursos de teoría de números y las plataformas de concursos usan un comprobador de seudoprimos de Euler–Jacobi para que los alumnos distingan mentirosos de Fermat de mentirosos de Solovay–Strassen sin implementar a mano la reciprocidad de Jacobi ni la exponenciación modular.
Los cuadernos de investigación y los barridos recreativos invocan el mismo contrato cuando necesitan un oráculo independiente para una lista publicada: quinientos sesenta y uno, mil ciento cinco, mil setecientos veintinueve y los demás ejemplos clásicos en base dos deben devolver verdadero, mientras que trescientos cuarenta y uno en base dos debe devolver falso.
Los talleres de criptografía que presentan la prueba de primalidad de Solovay–Strassen necesitan una herramienta que rechace n primo, porque el punto pedagógico es el compuesto que imita el criterio de Euler, no reiterar que los primos pasan. Los equipos de ingeniería que escriben pruebas de propiedades para sus propias bibliotecas de Jacobi o de potencia modular pueden fijar esta respuesta como contraste.
Prefiera esta herramienta cuando la pregunta sea estrictamente si un compuesto impar dado satisface la congruencia de Euler–Jacobi en una base dada, no cuando necesite un barrido de todas las bases, una prueba solo de Fermat, un informe de testigos Miller–Rabin o certificados para enteros de miles de bits.
Qué puede hacer con ella
Comprobaciones de aula de mentirosos de Solovay–Strassen
Haga que los alumnos envíen n igual a 561 con base 2 y confirmen una marca Euler–Jacobi verdadera; luego contrástela con 341 en base 2, que solo es mentiroso de Fermat.
Oráculo independiente para tablas publicadas
Valide listas sin conexión de seudoprimos de Euler–Jacobi frente a una implementación determinista de Jacobi más potencia modular.
Preguntas frecuentes
¿Qué hace que n sea seudoprimo de Euler–Jacobi en base a?
n debe ser impar y compuesto, gcd(a, n) debe ser 1, y a^((n−1)/2) debe ser congruente con el símbolo de Jacobi (a/n) módulo n.
¿Por qué se rechazan n par y n primo?
Los seudoprimos de Euler–Jacobi se definen como compuestos impares que imitan el criterio de Euler.
¿En qué se diferencia de un seudoprimo de Fermat?
Un seudoprimo de Fermat en base a solo necesita a^{n−1} ≡ 1 (mod n). La prueba de Euler–Jacobi exige además que la raíz cuadrada modular de esa condición de Fermat coincida con el símbolo de Jacobi. 341 es mentiroso de Fermat en base 2, pero no seudoprimo de Euler–Jacobi en base 2.
¿El 561 es seudoprimo de Euler–Jacobi en base 2?
Sí. Al elevar 2 a la potencia 280 y dividir entre 561 queda resto 1, y el símbolo de Jacobi de 2 sobre 561 también vale 1, así que la congruencia se cumple aunque 561 es compuesto. Es el menor número de Carmichael.
¿Qué pasa si la base comparte un factor con el número?
Entonces el número no es seudoprimo de Euler–Jacobi en esa base, porque la definición exige que ambos sean coprimos. La respuesta es no, y se muestra el divisor común para que vea el motivo.
Herramientas relacionadas
Para desarrolladores — acceso por API
Todo lo de esta página está disponible por programación. Esta sección es para equipos que quieren integrarlo en sus sistemas; el resto puede usar la herramienta de arriba sin más.
Endpoint de API
¿Prefiere automatizarlo? Un POST autenticado crea la tarea; el resultado llega por webhook o enlace firmado. La misma capacidad también se ejecuta aquí en la web, por email y desde Telegram — y pronto también desde nuestra app.
Llámela desde su stack
curl -X POST https://api.kit.forhosting.com/numth/euler-pseudoprime-check \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":561,"a":2}'const res = await fetch("https://api.kit.forhosting.com/numth/euler-pseudoprime-check", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 561,
"a": 2
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/euler-pseudoprime-check",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 561,
"a": 2
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/euler-pseudoprime-check", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":561,"a":2}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":561,"a":2}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/euler-pseudoprime-check", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Ejemplo de solicitud
{
"n": 561,
"a": 2
}Ejemplo de respuesta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.euler_pseudoprime_check",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}La API es asíncrona: la llamada devuelve un task_id al instante y el resultado llega por webhook. El polling está limitado a 1 req/s por tarea.
Precio
Precio publicado — sin tokens ni créditos inventados. Una tarea fallida no se cobra.
Límites
max_abs | 9007199254740991 |
Errores
| HTTP | Código | Significado |
|---|---|---|
401 | unauthorized | API key ausente o inválida. |
402 | insufficient_balance | El saldo no cubre el precio de la tarea. |
404 | unknown_type | El tipo de tarea no existe. |
429 | rate_limited | Demasiadas peticiones. Use el webhook en vez de sondear. |
Notas técnicas
Un n par o primo se rechaza con invalid_input en lugar de un falso negativo engañoso, porque la definición solo aplica a compuestos impares. El mismo módulo determinista funciona gratis en el navegador y en la ruta API a $0.002 por llamada exitosa.
Qué es un seudoprimo de Euler–Jacobi y en qué se diferencia de Fermat y Euler
La capacidad nunca llama primo a un compuesto ni seudoprimo a un primo: las entradas primas o pares son errores, y el booleano is_euler_jacobi_pseudoprime es verdadero solo cuando n es un compuesto impar admitido, el par es coprimo y se cumple la congruencia de Jacobi completa.
Contrato de entrada, campos de respuesta y comportamiento ante errores
Envíe un cuerpo JSON por POST con dos enteros obligatorios: n, el candidato compuesto impar (alias modulus y number), y a, la base (alias base). Cada campo puede llegar como número JSON o como cadena de dígitos decimales; los valores deben ser enteros completos cuyo valor absoluto quede dentro del rango seguro de enteros de JavaScript, de modo que la primalidad de n se decida con un conjunto fijo de testigos Miller–Rabin, determinista en ese bound. Campos ausentes, fracciones, booleanos, cadenas vacías y valores demasiado grandes fallan con invalid_input nombrando el campo. En caso de éxito el cuerpo devuelve n y a como números, informa gcd y el booleano coprime, devuelve jacobi en el conjunto menos uno, cero o uno, da exponent como (n menos uno) entre dos y remainder como a elevado a ese exponente módulo n, pone congruence_holds cuando remainder coincide con el símbolo de Jacobi reducido al sistema de residuos módulo n, y pone is_euler_jacobi_pseudoprime solo cuando el par es coprimo y la congruencia se cumple.
Dónde resulta útil un comprobador de seudoprimos de Euler–Jacobi
Como la capacidad es parse de nivel A puro, cada llamada exitosa es determinista, sin red y a $0.002, sin tokens de modelo. Mantenga n impar y compuesto, trate invalid_input como un arreglo del cliente y fije remainder y jacobi en las pruebas para que una refactorización futura no cambie en silencio el resultado modular.
Casos de integración
Pruebas de propiedades para bibliotecas de teoría de números
Fije gcd, el símbolo de Jacobi, remainder y el booleano en las pruebas unitarias para que una rutina local de reciprocidad no se desvíe de la definición.
Preguntas técnicas
¿Qué ocurre si gcd(a, n) es mayor que uno?
El par no es de Euler–Jacobi. La respuesta aún devuelve gcd, jacobi 0 y el resto modular, pero is_euler_jacobi_pseudoprime es falso porque la definición exige coprimalidad.
¿Cuánto cuesta el comprobador de seudoprimos de Euler–Jacobi?
La herramienta del navegador es gratuita. Las peticiones API usan saldo prepago KIT a $0.002 por llamada exitosa; la entrada inválida no se factura.