In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and (where mod refers to the modulo operation). The motivation for this definition is the fact that all prime numbers p satisfy the above equation which can be deduced from Fermat's little theorem. Fermat's theorem asserts that if p is prime, and coprime to a, then ap−1 ≡ 1 (mod p). Suppose that p>2 is prime, then p can be expressed as 2q + 1 where q is an integer. Thus, a(2q+1) − 1 ≡ 1 (mod p), which means that a2q − 1 ≡ 0 (mod p). This can be factored as (aq − 1)(aq + 1) ≡ 0 (mod p), which is equivalent to a(p−1)/2 ≡ ±1 (mod p).
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Eulersche Pseudoprimzahl (de)
- Número pseudoprimo de Euler (es)
- Euler pseudoprime (en)
- Pseudoprimo di Eulero (it)
- Nombre pseudo-premier d'Euler (fr)
- 欧拉伪素数 (zh)
|
| rdfs:comment
| - Eine ungerade natürliche Zahl n wird eulersche Pseudoprimzahl genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu ihr teilerfremde Basis a wie eine Primzahl verhält: wenn nämlich die Kongruenz erfüllt ist. Anders ausgedrückt muss n die Differenz oder die Summe teilen. (de)
- 欧拉伪素数（英語：Euler pseudoprime）是伪素数的一种。对于奇合数n以及与其互素的自然数a，如果 成立，则称n为关于a的欧拉伪素数。欧拉伪素数是费马伪素数的推广，所有欧拉伪素数同时也是费马伪素数。 与费马伪素数类似，欧拉伪素数的定义也是源于费马小定理。该定理表明，对于素数p以及整数a，有 ap−1 = 1 (mod p)。对大于2的素数p，p可以表示为2q + 1 ，其中q为整数。于是a(2q+1) − 1 = 1 (mod p) 成立。再进一步化简为a2q − 1 = 0 (mod p)。通过因式分解，得到(aq − 1)(aq + 1) = 0 (mod p)，即a(p−1)/2 = ±1 (mod p)。 上式可以用作概率素性检验，其可靠性是费马素性检验的两倍。不过无法基于欧拉伪素数对素数进行确定性检验，因为存在绝对欧拉伪素数，即其关于所有与其互素的数都是欧拉伪素数。绝对欧拉伪素数是卡迈克尔数（即绝对费马伪素数）的子集。最小的绝对欧拉伪素数为1729 = 7×13×19。 (zh)
- In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and (where mod refers to the modulo operation). The motivation for this definition is the fact that all prime numbers p satisfy the above equation which can be deduced from Fermat's little theorem. Fermat's theorem asserts that if p is prime, and coprime to a, then ap−1 ≡ 1 (mod p). Suppose that p>2 is prime, then p can be expressed as 2q + 1 where q is an integer. Thus, a(2q+1) − 1 ≡ 1 (mod p), which means that a2q − 1 ≡ 0 (mod p). This can be factored as (aq − 1)(aq + 1) ≡ 0 (mod p), which is equivalent to a(p−1)/2 ≡ ±1 (mod p). (en)
- En aritmética, un número entero compuesto impar n se llama pseudoprimo de Euler en base a, si a y n son números coprimos, y (donde mod se refiere a la operación módulo). La motivación de esta definición es el hecho de que todos los números primos p satisfacen la ecuación anterior que puede deducirse del pequeño teorema de Fermat, que afirma que si p es primo y coprimo de a, entonces ap−1 ≡ 1 (mod p). (es)
- En mathématiques, un nombre pseudo-premier d'Euler de base a est un nombre composé impair n premier avec a et tel que la congruence suivante soit vérifiée : Cette définition est motivée par le critère d'Euler (qui précise le petit théorème de Fermat), d'après lequel si n est un nombre premier impair premier avec a, cette congruence a lieu. La relation peut être vérifiée assez rapidement, ce qui est utilisé pour les tests de primalité. Ces tests sont deux fois plus forts que les tests basés sur le petit théorème de Fermat. (fr)
- Un numero n è detto pseudoprimo di Eulero in base a (con MCD(n,a)=1) se è un numero dispari composto e dove mod è l'operazione modulo. Questi numeri sono detti pseudoprimi perché tutti i numeri primi verificano questa proprietà, in base al piccolo teorema di Fermat. Infatti, secondo questo ogni numero a coprimo con n verifica Se ora p>2, si ha , ovvero Una forma più forte della relazione precedente è Invece, . La differenza dei due casi (pseudoprimi di Eulero o di Eulero-Jacobi) si trova nella scelta di +1 o -1, che rende più raffinata la valutazione di Eulero-Jacobi. (it)
|
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and (where mod refers to the modulo operation). The motivation for this definition is the fact that all prime numbers p satisfy the above equation which can be deduced from Fermat's little theorem. Fermat's theorem asserts that if p is prime, and coprime to a, then ap−1 ≡ 1 (mod p). Suppose that p>2 is prime, then p can be expressed as 2q + 1 where q is an integer. Thus, a(2q+1) − 1 ≡ 1 (mod p), which means that a2q − 1 ≡ 0 (mod p). This can be factored as (aq − 1)(aq + 1) ≡ 0 (mod p), which is equivalent to a(p−1)/2 ≡ ±1 (mod p). The equation can be tested rather quickly, which can be used for probabilistic primality testing. These tests are twice as strong as tests based on Fermat's little theorem. Every Euler pseudoprime is also a Fermat pseudoprime. It is not possible to produce a definite test of primality based on whether a number is an Euler pseudoprime because there exist absolute Euler pseudoprimes, numbers which are Euler pseudoprimes to every base relatively prime to themselves. The absolute Euler pseudoprimes are a subset of the absolute Fermat pseudoprimes, or Carmichael numbers, and the smallest absolute Euler pseudoprime is 1729 = 7×13×19. (en)
- Eine ungerade natürliche Zahl n wird eulersche Pseudoprimzahl genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu ihr teilerfremde Basis a wie eine Primzahl verhält: wenn nämlich die Kongruenz erfüllt ist. Anders ausgedrückt muss n die Differenz oder die Summe teilen. (de)
- En aritmética, un número entero compuesto impar n se llama pseudoprimo de Euler en base a, si a y n son números coprimos, y (donde mod se refiere a la operación módulo). La motivación de esta definición es el hecho de que todos los números primos p satisfacen la ecuación anterior que puede deducirse del pequeño teorema de Fermat, que afirma que si p es primo y coprimo de a, entonces ap−1 ≡ 1 (mod p). Supóngase que p>2 es primo. Entonces, p se puede expresar como 2q + 1 donde q es un número entero. Así, a(2q+1) − 1 ≡ 1 (mod p), lo que significa que a2q − 1 ≡ 0 (mod p). Esto se puede factorizar como (aq − 1)(aq + 1) ≡ 0 (mod p), que es equivalente a a(p−1)/2 ≡ ±1 (mod p). La ecuación se puede probar con bastante rapidez, lo que se puede usar para pruebas de primalidad probabilísticas. Estas pruebas son dos veces más fuertes que las pruebas basadas en el pequeño teorema de Fermat. Todo número pseudoprimo de Euler es también un . No es posible producir una prueba definitiva de primalidad basada en si un número es un pseudoprimo de Euler porque existen "pseudoprimos de Euler absolutos", números que son pseudoprimos de Euler para todas las bases primas entre sí. Los pseudoprimos absolutos de Euler son un subconjunto de los pseudoprimos absolutos de Fermat, o números de Carmichael, y el pseudoprimo absoluto de Euler más pequeño es 1729 = 7 × 13 × 19. (es)
- En mathématiques, un nombre pseudo-premier d'Euler de base a est un nombre composé impair n premier avec a et tel que la congruence suivante soit vérifiée : Cette définition est motivée par le critère d'Euler (qui précise le petit théorème de Fermat), d'après lequel si n est un nombre premier impair premier avec a, cette congruence a lieu. La relation peut être vérifiée assez rapidement, ce qui est utilisé pour les tests de primalité. Ces tests sont deux fois plus forts que les tests basés sur le petit théorème de Fermat. Tout nombre pseudo-premier d'Euler est aussi un nombre pseudo-premier de Fermat. Il n'est pas possible de produire un test définitif de primalité basé sur l'éventualité qu'un nombre soit un pseudo-premier d'Euler parce qu'il existe des nombres pseudo-premiers absolus d'Euler, qui sont des pseudo-premiers d'Euler pour chaque base relativement première à elles-mêmes. Les nombres pseudo-premiers absolus d'Euler sont un sous-ensemble des pseudo-premiers de Fermat absolus, ou nombres de Carmichael. Le plus petit pseudo-premier absolu d'Euler est 1729 = 7 × 13 × 19. La condition plus forteoù pgcd(a, n) = 1 et est le symbole de Jacobi, est quelquefois prise comme définition d'un pseudo-premier d'Euler. Une discussion sur les nombres de cette forme peut être trouvée dans l'article « Nombre pseudo-premier d'Euler-Jacobi ». (fr)
- Un numero n è detto pseudoprimo di Eulero in base a (con MCD(n,a)=1) se è un numero dispari composto e dove mod è l'operazione modulo. Questi numeri sono detti pseudoprimi perché tutti i numeri primi verificano questa proprietà, in base al piccolo teorema di Fermat. Infatti, secondo questo ogni numero a coprimo con n verifica Se ora p>2, si ha , ovvero Una forma più forte della relazione precedente è dove (a/n) è il simbolo di Legendre. Un numero che verifica questa uguaglianza è detto pseudoprimo di Eulero-Jacobi in base a. Ogni pseudoprimo di Eulero-Jacobi è anche uno pseudoprimo di Eulero, poiché il simbolo di Legendre può essere solamente 1 e -1, tuttavia esistono numeri del secondo tipo che non appartengono al primo insieme. Ad esempio 9 è uno pseudoprimo di Eulero in base 17, ma non uno pseudoprimo di Eulero-Jacobi; mentre in base 19 è uno pseudoprimo di Eulero e di Eulero-Jacobi. Infatti: Invece, . La differenza dei due casi (pseudoprimi di Eulero o di Eulero-Jacobi) si trova nella scelta di +1 o -1, che rende più raffinata la valutazione di Eulero-Jacobi. Ogni pseudoprimo di Eulero è anche uno pseudoprimo di Fermat in base a, ma non vale il viceversa. Esistono inoltre numeri che sono pseudoprimi di Eulero in ogni base a coprima con loro stessi; tali numeri sono detti pseudoprimi assoluti di Eulero. Questi numeri sono un sottoinsieme degli pseudoprimi assoluti di Fermat, generalmente chiamati numeri di Carmichael. Il più piccolo pseudoprimo assoluto di Eulero è 1729. (it)
- 欧拉伪素数（英語：Euler pseudoprime）是伪素数的一种。对于奇合数n以及与其互素的自然数a，如果 成立，则称n为关于a的欧拉伪素数。欧拉伪素数是费马伪素数的推广，所有欧拉伪素数同时也是费马伪素数。 与费马伪素数类似，欧拉伪素数的定义也是源于费马小定理。该定理表明，对于素数p以及整数a，有 ap−1 = 1 (mod p)。对大于2的素数p，p可以表示为2q + 1 ，其中q为整数。于是a(2q+1) − 1 = 1 (mod p) 成立。再进一步化简为a2q − 1 = 0 (mod p)。通过因式分解，得到(aq − 1)(aq + 1) = 0 (mod p)，即a(p−1)/2 = ±1 (mod p)。 上式可以用作概率素性检验，其可靠性是费马素性检验的两倍。不过无法基于欧拉伪素数对素数进行确定性检验，因为存在绝对欧拉伪素数，即其关于所有与其互素的数都是欧拉伪素数。绝对欧拉伪素数是卡迈克尔数（即绝对费马伪素数）的子集。最小的绝对欧拉伪素数为1729 = 7×13×19。 (zh)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)