Função tociente de Euler

Na teoria dos números, Função totient de Euler conta os inteiros positivos até um determinado inteiro n que são relativamente primos n. É escrito usando a letra grega phi como $(n)}$ ou $(n)}$, e também pode ser chamado Função de phi de Euler. Em outras palavras, é o número de inteiros k no intervalo 1 ≤ k ≤ n para o qual o maior divisor comum Gcd(n, k) é igual a 1. Os inteiros k desta forma são por vezes referidos como totativos de n.

Por exemplo, os totais de n = 9 são os seis números 1, 2, 4, 5, 7 e 8. Eles são todos relativamente primo a 9, mas os outros três números neste intervalo, 3, 6 e 9, não são, pois gcd(9, 3) = gcd(9, 6) = 3 e gcd(9, 9) = 9. Portanto, φ(9) = 6. Como outro exemplo, φ(1) = 1 já que para n = 1< /span> o único número inteiro no intervalo de 1 a n é o próprio 1, e gcd (1, 1) = 1.

A função totient de Euler é uma função multiplicativa, o que significa que se dois números m e n são relativamente primos, então φ(Mn.) = φ(m)φ(n). Esta função dá a ordem do grupo multiplicador de inteiros modulo n (o grupo de unidades do anel ${displaystyle mathbb {Z} /nmathbb {Z} }$). Também é usado para definir o sistema de criptografia RSA.

História, terminologia e notação

Leonhard Euler introduziu a função em 1763. No entanto, naquela época ele não escolheu nenhum símbolo específico para denotá-la. Em uma publicação de 1784, Euler estudou mais a função, escolhendo a letra grega π para denota-la: ele escreveu πD para "a multidão de números menores que D, e que não possuem divisor comum com ele". Esta definição varia da definição atual para a função totient em D = 1 mas, fora isso, é a mesma. A notação agora padrão φ(A) vem do tratado de Gauss de 1801 Disquisitiones Arithmeticae, embora Gauss não tenha usado parênteses em torno do argumento e tenha escrito φA. Assim, é frequentemente chamada de função phi de Euler ou simplesmente função phi.

Em 1879, J. J. Sylvester cunhou o termo totiente para esta função, por isso também é chamada de função totiente de Euler, a função totiente de Euler, a função totiente de Euler. totiente ou totiente de Euler. O tociente de Jordan é uma generalização do tociente de Euler.

O cotociente de n é definido como n − φ(n). Conta o número de inteiros positivos menores ou iguais a n que possuem pelo menos um fator primo em comum com n.

Calculando a função totiente de Euler

Existem diversas fórmulas para calcular φ(n).

Fórmula do produto de Euler

Afirma

${displaystyle varphi (n)=nprod _{pmid n}left(1-{frac {1}{p}}right),}$

onde o produto está sobre os números primos distintos que dividem n. (Para notação, consulte Função aritmética.)

Uma formulação equivalente é

$${displaystyle varphi (n)=p_{1}^{k_{1}-1}(p_{1}{-}1),p_{2}^{k_{2}-1}(p_{2}{-}1)cdots p_{r}^{k_{r}-1}(p_{r}{-}1),}$$

$Não. n=p_{1}^{k_{1}}p_{2}^{k_{2}}cdots p_{r}^{k_{r}}}$

$Não.$

${displaystyle p_{1},p_{2},ldotsp_{r}}$

A prova destas fórmulas depende de dois fatos importantes.

Phi é uma função multiplicativa

Isso significa que se gcd(m, n) = 1, então φ(m) φ(n) = φ( mn). Esboço da prova: Seja A, B, C são os conjuntos de inteiros positivos que são primos e menores que m, n, mn, respectivamente, de modo que |A| = φ(m), etc. Então há uma bijeção entre A × < i>B e C pelo teorema do resto chinês.

Valor de phi para um argumento de potência principal

Se p for primo e k ≥ 1< /span>, então

${displaystyle varphi left(p^{k}right)=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}left(1-{tfrac {1}{p}}right.}$

Prova: Como p é um número primo, os únicos valores possíveis de gcd(p^k, m) são 1, p, p²,..., p^k , e a única maneira de ter gcd(p^{k, m)> 1} é se m é um múltiplo de p, ou seja, m ∈ {p, 2p, 3p,..., p^{k − 1}p = p^k}, e há p^{< i>k − 1} tais múltiplos não maiores que p^{k< /sup>}. Portanto, o outro p^k − p ^{k − 1} números são todos relativamente primos a p^k.

Prova da fórmula do produto de Euler

O teorema fundamental da aritmética afirma que se n > 1 há uma expressão única $Não. n=p_{1}^{k_{1}}p_{2}^{k_{2}}cdots p_{r}^{k_{r}},}$ Onde? p₁ < p₂ <... p_R são números primos e cada um k_Eu... ≥ 1. (O caso n = 1 corresponde ao produto vazio.) Repetidamente usando a propriedade multiplicativa de φ e a fórmula para φ(p^k) dá

${displaystyle {begin{array}{rcl}varphi (n)&=&varphi (p_{1}^{k_{1}}),varphi (p_{2}^{k_{2}})cdots varphi (p_{r}^{k_{r}})\[1em]&p_{1}^{k_{1}}left(1-{frac {1}{p_{1}}}right)p_{2}^{k_{2}}left(1-{frac {1}{p_{2}}}right)cdots p_{r}^{k_{r}}left(1-{frac {1}{p_{r}}}right)[.1em]&=&p_{1}^{k_{1}}p_{2}^{k_{2}}cdots p_{r}^{k_{r}}left(1-{frac {1}{p_{1}}}right)left(1-{frac {1}{p_{2}}}right)cdots left(1-{frac {1}{p_{r}}}right)[.1em]&=&nleft(1-{frac {1}{p_{1}}}right)left(1-{frac {1}{p_{2}}}right)cdots left(1-{frac {1}{p_{r}}}right).end{array}}}$

Isso dá as duas versões da fórmula de produto da Euler.

Uma prova alternativa que não requer a propriedade multiplicativa, em vez disso, usa o princípio de inclusão-exclusão aplicado ao conjunto ${displaystyle {1,2,ldotsn}}$, excluindo os conjuntos de inteiros divisíveis pelos principais divisores.

Exemplo

${displaystyle varphi (20)=varphi (2^{2}5)=20,(1-{tfrac {1}{2}},(1-{tfrac {1}{5}}=20cdot {tfrac {1}{2}}cdot {tfrac {1}{2}}cdot {displaystyle {tfrac {1}{2}}cdot}{5}}}=20cdot {tfrac {1}{2}}}cdot {1}}{5}}}}=20cdot {1}}}}}}}{2}{2}}}}=2}}}}}}=2}}=2}}=2}}}=2}}}}=2}=2}=2}=2}=2}=2}=2}=2}=2} {4}{5}}=8.}$

Em palavras: os fatores primos distintos de 20 são 2 e 5; metade dos vinte números inteiros de 1 a 20 são divisíveis por 2, restando dez; um quinto deles é divisível por 5, deixando oito números coprimos com 20; estes são: 1, 3, 7, 9, 11, 13, 17, 19.

A fórmula alternativa usa apenas números inteiros:

$${displaystyle varphi (20)=varphi (2^{2}5^{1})=2^{2-1}(2{-}1),5^{1-1}(5{-}1)=2cdot 1cdot 1cdot 4=8.}$$

Transformada de Fourier

O totiente é a transformada discreta de Fourier do mdc, avaliada em 1. Seja

${displaystyle {mathcal {F}}{mathbf {x} }[m]=sum limits _{k=1}^{n}x_{k}cdot e^{{-2pi Eu... Não.$

onde x_k = gcd(k,n)< /span> para k ∈ {1,..., n}. Então

${displaystyle varphi (n)={mathcal {F}}{mathbf {x} }[1]=sum limits _{k=1}^{n}gcd(k,n)e^{-2pi i{frac Não.$

A parte real desta fórmula é

${displaystyle varphi (n)=sum limits _{k=1}^{n}gcd(k,n)cos {tfrac (em inglês) k}{n}}.}$

Por exemplo, usando ${displaystyle cos} - Sim. frac{5}} ? Não. {5}+1}{4}}}$ e ${displaystyle cos {tfrac {2pi} frac{5}} ? Não. {5}-1}{4}}}}$:

$$(em inglês) {displaystyle {begin{array}{rcl}varphi (10)&=&gcd(1,10)cos {tfrac {2pi }{10}}+gcd(2,10)cos {tfrac {4pi }{10}}+gcd(3,10)cos {6pi }{10}}+cdot {5}}+1}{4}}+2cdot ({tfrac {{sqrt) {5}}-1}{4}})+1cdot (-{tfrac {{sqrt {5}}-1}{4}}+2cdot (-{tfrac {{sqrt {5}}+1}{4}})+5cdot (-1)&+2cdot (-{tfrac {{sqrt {5}}+1}{4}})+1cdot (-{tfrac {{sqrt {5}}-1}{4}})+2cdot ({tfrac {{sqrt) {5}}-1}{4}})+1cdot ({tfrac {{sqrt) {5}}+1}{4}})+10cdot (1)&=&4.end{array}}}$$

Soma divisora

A propriedade estabelecida por Gauss, que

${displaystyle sum _{dmid n}varphi (d)=n,}$

onde a soma é sobre todos os divisores positivos d de n, pode ser provado de diversas maneiras. (Consulte Função aritmética para convenções de notação.)

Uma prova é notar que φ(d) também é igual ao número de possíveis geradores do grupo cíclico C_d; especificamente, se C_d = ⟨g⟩ com g^d = 1, então g^k é um gerador para cada k< /span> coprime para d. Como cada elemento de C_n gera um subgrupo cíclico, e todos os subgrupos C_d ⊆ C_n são gerados precisamente por elementos φ(d) de C_n, segue a fórmula. Equivalentemente, a fórmula pode ser derivada pelo mesmo argumento aplicado ao grupo multiplicativo das n-ésimas raízes da unidade e das d-ésimas raízes primitivas da unidade.

A fórmula também pode ser derivada da aritmética elementar. Por exemplo, seja n = 20 e considere as frações positivas até 1 com denominador 20:

${20} fract {1}{20}},{tfrac {2}{20}},{tfrac {3}{20}},,{tfrac {4}{20}},{tfrac {5}{20}},,{tfrac {6}{20}},,{tfrac {7}{20}},,{tfrac {8}{20}}$

Coloque-os em termos mais baixos:

${1}{20},tfrac {1}{5}},tfrac {1}{10}},,{tfrac {1}{5}},,{tfrac {1}{4}},,{tfrac {3}{10}},,{tfrac {7}{20}},,{tfrac {2}{5}}} Não.$

Essas vinte frações são todas k/d ≤ 1 cujos denominadores são os divisores d = 1, 2, 4, 5, 10, 20. As frações com 20 como denominador são aquelas com numeradores relativamente primos a 20, nomeadamente 1/20, 3< /span>/20, 7/20, 9/20, 11/20, 13/20, 17< /span>/20, 19/20; por definição, são φ(20) frações. Da mesma forma, existem frações φ(10) com denominador 10 e φ(5) frações com denominador 5, etc. Assim, o conjunto de vinte frações é dividido em subconjuntos de tamanho φ(d) para cada d dividindo 20. Um argumento semelhante se aplica a qualquer n.

A inversão de Möbius aplicada à fórmula da soma dos divisores dá

${displaystyle varphi (n)=sum _{dmid n}mu left(dright)cdot {frac - Não. _{dmid n}{frac {mu (d)}{d}},}$

Onde? μ é a função Möbius, a função multiplicativa definida por ${displaystyle mu (p)=-1}$ e ${displaystyle mu (p^{k})=0}$ para cada primo p e k ≥ 2. Esta fórmula também pode ser derivada da fórmula do produto, multiplicando-se ${textstyle prod _{pmid n}(1-{frac {1}{p}}}$ para começar ${textstyle sum _{dmid n}{frac {mu (d)}{d}}.}$

Um exemplo:

$$(em inglês) {displaystyle {begin{aligned}varphi (20)&=mu (1)cdot 20+mu (2)cdot 10+mu (4)cdot 5+mu (5)cdot 4+mu (10)cdot 2+mu (20)cdot 1\[5em]&=1cdot 20-1cdot 10+0cdot$$

Alguns valores

Os primeiros 100 valores (sequência A000010 no OEIS) são mostrados na tabela e no gráfico abaixo:

φ(n) para 1 ≤ n ≤ 100

+	1	2	3	4	5	6	7	8	9	10.
0	1	1	2	2	4	2	6	4	6	4
10.	10.	4	12	6	8	8	16.	6	18.	8
20.	12	10.	22	8	20.	12	18.	12	28	8
30	30	16.	20.	16.	24.	12	36	18.	24.	16.
40	40	12	42	20.	24.	22	46.	16.	42	20.
50	32	24.	52	18.	40	24.	36	28	58	16.
60	60	30	36	32	48	20.	66	32	44	24.
70	70	24.	72	36	40	36	60	24.	78	32
80	54	40	82	24.	64	42	56	40	88	24.
90	72	44	60	46.	72	32	96	42	60	40

No gráfico à direita a linha superior Sim. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = n - 1 é um limite superior válido para todos n diferente de um, e alcançou se e somente se n é um número primo. Um limite inferior simples é ${displaystyle varphi (n)geq {sqrt {n/2}}}$, que é bastante solto: na verdade, o limite inferior do gráfico é proporcional a n/log de log n.

Teorema de Euler

Isso afirma que se a e n são relativamente primos então

${displaystyle a^{varphi (n)}equiv 1mod n.}$

O caso especial onde n é primo é conhecido como pequeno teorema de Fermat.

Isso decorre do teorema de Lagrange e do fato de que φ(n) é a ordem de o grupo multiplicativo de inteiros módulo n.

O criptossistema RSA é baseado neste teorema: ele implica que o inverso da função a ↦ a^e mod n, onde e é o expoente de criptografia (público), é a função b ↦ b^d mod n, onde d, o expoente de descriptografia (privado), é o inverso multiplicativo de e módulo φ(n). A dificuldade de calcular φ(n) sem conhecer a fatoração de n é, portanto, a dificuldade de calcular d: isso é conhecido como RSA problema que pode ser resolvido fatorando n. O proprietário da chave privada conhece a fatoração, uma vez que uma chave privada RSA é construída escolhendo n como o produto de dois (aleatoriamente escolhido) números primos grandes p e q< /span>. Apenas n é divulgado publicamente, e dada a dificuldade de fatorar números grandes temos a garantia de que ninguém mais conhece a fatoração.

Outras fórmulas

• ${displaystyle amid bimplies varphi (a)mid varphi (b)}$
• ${displaystyle mmid varphi (a^{m}-1)}$
• ${displaystyle varphi (mn)=varphi (m)varphi (n)cdot {frac {d}{varphi (d)}}quad {text{where }}d=operatorname {gcd} (m,n)}$

  In particular:

  • ${displaystyle varphi (2m)={begin{cases}2varphi (m)&{text{ if }}m{text{ is even}}\varphi (m)&{text{ if }}m{text{ is odd}}end{cases}}}$
  • ${displaystyle varphi left(n^{m}right)=n^{m-1}varphi (n)}$
• ${displaystyle varphi (operatorname {lcm} (m,n))cdot varphi (operatorname {gcd} (m,n))=varphi (m)cdot varphi (n)}$

  Compare this to the formula ${textstyle operatorname {lcm} (m,n)cdot operatorname {gcd} (m,n)=mcdot n}$ (see least common multiple).

• φ(n) is even for n ≥ 3.

  Moreover, if n has r distinct odd prime factors, 2^r | φ(n)

• For any a > 1 and n > 6 such that 4 ∤ n there exists an l ≥ 2n such that l | φ(aⁿ − 1).
• ${displaystyle {frac {varphi (n)}{n}}={frac {varphi (operatorname {rad} (n))}{operatorname {rad} (n)}}}$

  where rad(n) is the radical of n (the product of all distinct primes dividing n).

• ${displaystyle sum _{dmid n}{frac {mu ^{2}(d)}{varphi (d)}}={frac {n}{varphi (n)}}}$
• ${displaystyle sum _{1leq kleq n atop (k,n)=1}!!k={tfrac {1}{2}}nvarphi (n)quad {text{for }}n>1}$
• ${displaystyle sum _{k=1}^{n}varphi (k)={tfrac {1}{2}}left(1+sum _{k=1}^{n}mu (k)leftlfloor {frac {n}{k}}rightrfloor ^{2}right)={frac {3}{pi ^{2}}}n^{2}+Oleft(n(log n)^{frac {2}{3}}(log log n)^{frac {4}{3}}right)}$ (cited in)
• ${displaystyle sum _{k=1}^{n}{frac {varphi (k)}{k}}=sum _{k=1}^{n}{frac {mu (k)}{k}}leftlfloor {frac {n}{k}}rightrfloor ={frac {6}{pi ^{2}}}n+Oleft((log n)^{frac {2}{3}}(log log n)^{frac {4}{3}}right)}$
• ${displaystyle sum _{k=1}^{n}{frac {k}{varphi (k)}}={frac {315,zeta (3)}{2pi ^{4}}}n-{frac {log n}{2}}+Oleft((log n)^{frac {2}{3}}right)}$
• ${displaystyle sum _{k=1}^{n}{frac {1}{varphi (k)}}={frac {315,zeta (3)}{2pi ^{4}}}left(log n+gamma -sum _{p{text{ prime}}}{frac {log p}{p^{2}-p+1}}right)+Oleft({frac {(log n)^{frac {2}{3}}}{n}}right)}$

  (where γ is the Euler–Mascheroni constant).

• ${displaystyle sum _{stackrel {1leq kleq n}{operatorname {gcd} (k,m)=1}}!!!!1=n{frac {varphi (m)}{m}}+Oleft(2^{omega (m)}right)}$

  where m > 1 is a positive integer and ω(m) is the number of distinct prime factors of m.

Identidade de Menon

Em 1965, P. Kesava Menon provou

${displaystyle sum _{stackrel {1leq kleq n}{gcd(k,n)=1}}!!!!gcd(k-1,n)=varphi (n)d(n),}$

onde d(n) = σ0(n) é o número de divisores de n.

Gerando funções

A série de Dirichlet para φ(n) pode ser escrita em termos da função zeta de Riemann como:

${displaystyle sum _{n=1}^{infty }{frac {varphi (n)}{n^{s}}}={frac {zeta (s-1)}{zeta (s)}}}$

onde o lado esquerdo converge para $(s)>2}$.

A função geradora da série de Lambert é

${displaystyle sum _{n=1}^{infty }{frac {varphi (n)q^{n}}{1-q^{n}}}={frac {q}{(1-q)^{2}}$

que converge para |q< /span>| < 1.

Ambos são comprovados por manipulações de séries elementares e pelas fórmulas para φ(n).

Taxa de crescimento

Nas palavras de Hardy & Wright, a ordem de φ(n) é "sempre 'quase n'."

Primeiro

${displaystyle lim sup {frac {varphi (n)}{n}}=1,}$

mas como n vai para o infinito, para todos os δ > 0

$(n)}{n^{1-delta }}}rightarrow infty.}$

Essas duas fórmulas podem ser provadas usando pouco mais do que as fórmulas para φ(n) e o divisor função de soma σ(n).

Na verdade, durante a prova da segunda fórmula, a desigualdade

${displaystyle {frac {6}{pi ^{2}}}<{frac {varphi (n)sigma (n)}{n^{2}}}<1,}$

verdadeiro para n > 1, está provado.

Também temos

${displaystyle lim inf {frac {varphi (n)}{n}}log n=e^{-gamma }$

Aqui γ é a constante de Euler, γ = 0,577215665..., então e^γ = 1,7810724... e e^−γ = 0,56145948....

Provar isso não requer exatamente o teorema dos números primos. Como log log n vai para o infinito, esta fórmula mostra que

${displaystyle lim inf {frac {varphi (n)}{n}}=0.}$

Na verdade, mais é verdade.

${displaystyle varphi (n)>{frac {n}{e^{gamma };log log n+{frac {3}{log log n}}quad {text{for }}n>2}$

e

${displaystyle varphi (n)<{frac Não. }log log n}}quad {text{para infinitamente muitos }}n.}$

A segunda desigualdade foi mostrada por Jean-Louis Nicolas. Ribenboim diz que “O método de prova é interessante, na medida em que a desigualdade é mostrada primeiro sob a suposição de que a hipótese de Riemann é verdadeira e, em segundo lugar, sob a suposição contrária”.

Para o pedido médio, temos

${displaystyle varphi (1)+varphi (2)+cdots +varphi (n)={frac {3n^{2}}{pi ^{2}}}+Oleft(n(log n)^{frac {2}{3}}(loglog n)^{frac {4}{3}}rightarrow infty}$

devido a Arnold Walfisz, sua prova explorando estimativas em somas exponenciais devidas a I. M. Vinogradov e N. M. Korobov. Por uma combinação dos métodos de van der Corput e Vinogradov, H.-Q. Liu (Sobre a função de Euler.Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775) melhorou o termo de erro para

${displaystyle Oleft(n(log n)^{frac {2}{3}}(log log n)^{frac {1}{3}}right)}$

(esta é atualmente a estimativa mais conhecida deste tipo). O 'Grande O' representa uma quantidade que é limitada por uma constante vezes a função de n dentro dos parênteses (que é pequeno comparado a n²).

Este resultado pode ser usado para provar que a probabilidade de dois números escolhidos aleatoriamente serem relativamente primos é 6< span class="sr-only">/π² .

Proporção de valores consecutivos

Em 1950, Somayajulu provou

${displaystyle {begin{aligned}lim inf {frac {varphi (n+1)}{varphi (n)}}&=0quad {text{and}}\[5px]lim sup {frac {varphi (n+1)}{varphi (n)}}&=infty.end{aligned}}}$

Em 1954, Schinzel e Sierpiński reforçaram isso, provando que o conjunto

${displaystyle left{{frac {varphi (n+1)}{varphi (n)}},; n=1,2,ldots right}}$

é denso nos números reais positivos. Eles também provaram que o conjunto

${displaystyle left{{frac {varphi (n)}{n}},;n=1,2,ldots right}}$

é denso no intervalo (0,1).

Números de pacientes

Um número totiente é um valor da função totiente de Euler: ou seja, um m< /span> para o qual existe pelo menos um n para o qual φ(n) = m. A valência ou multiplicidade de um número tociente m é o número de soluções para esta equação. Um não-totiente é um número natural que não é um número totiente. Todo número inteiro ímpar que exceda 1 é trivialmente um não-cliente. Existem também infinitos números pares de não-clientes e, de fato, todo número inteiro positivo tem um múltiplo que é um não-cliente par.

O número de números totientes até um determinado limite x é

${displaystyle {frac {x}{log x}}e^{{big (}C+o(1){big)}(log log x^{2}}}$

para uma constante C = 0,8178146....

Se contado de acordo com a multiplicidade, o número de números totientes até um determinado limite x é

$Não. }{n:varphi (n)leq x}{Big vert }={frac {zeta (2)zeta (3)}{zeta (6)}}cdot x+R(x)}$

onde o termo de erro R é de ordem no máximo x/(log x)^k para qualquer k.

Sabe-se que a multiplicidade de m excede m^δ com frequência infinita para qualquer δ < 0,55655.

Teorema de Ford

Ford (1999) provou que para cada número inteiro k ≥ 2 existe um número totiente m de multiplicidade k: isto é, para o qual a equação φ(n) = m tem exatamente k soluções; este resultado já havia sido conjecturado por Wacław Sierpiński, e foi obtido como consequência da hipótese H de Schinzel. Na verdade, cada multiplicidade que ocorre, o faz com uma frequência infinita.

No entanto, nenhum número m é conhecido com multiplicidade k = 1. A conjectura da função totiente de Carmichael é a afirmação de que não existe tal m.

Números de tocientes perfeitos

Um número tociente perfeito é um número inteiro igual à soma de seus tocientes iterados. Ou seja, aplicamos a função tociente a um número n, aplicamos novamente ao tociente resultante, e assim por diante, até atingir o número 1, e somamos a sequência de números resultante; se a soma for igual a n, então n é um número tociente perfeito.

Aplicativos

Ciclotomia

Na última seção das Disquisitiones, Gauss prova que um n-gon regular pode ser construído com régua e compasso se < span class="texhtml">φ(n) é uma potência de 2. Se n é uma potência de um número primo ímpar a fórmula para o totiente diz que seu totiente pode ser uma potência de dois apenas se n é uma primeira potência e n − 1 é uma potência de 2. Os primos que são um a mais que uma potência de 2 são chamados de primos de Fermat, e apenas cinco são conhecidos: 3, 5, 17, 257 e 65537. Fermat e Gauss sabiam disso. Ninguém foi capaz de provar se existem mais.

Assim, um n-gon regular tem uma construção com régua e compasso se n é um produto de primos de Fermat distintos e qualquer potência de 2. Os primeiros n são

2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,... (sequência A003401 no OEIS).

Teorema dos números primos para progressões aritméticas

O criptossistema RSA

Configurar um sistema RSA envolve escolher grandes números primos p e q, computando n = pq e k = φ(n) e encontrar dois números e e d tais que ed ≡ 1 (mod k). Os números n e e (a "chave de criptografia") são divulgadas ao público, e d (a " chave de descriptografia") é mantida privada.

Uma mensagem, representada por um número inteiro m, onde 0 < m < n, é criptografado pela computação S = m^e (mod n).

Ele é descriptografado computando t = S^d (mod n). O Teorema de Euler pode ser usado para mostrar que se 0 < t < n, então t = m.

A segurança de um sistema RSA seria comprometida se o número n pudesse ser fatorado de forma eficiente ou se φ(n) poderia ser calculado de forma eficiente sem fatorar n.

Problemas não resolvidos

Conjectura de Lehmer

Se p for primo, então φ(< i>p) = p − 1. Em 1932, D. H. Lehmer perguntou se existem números compostos n tais que φ(n) divide n − 1. Nenhum é conhecido.

Em 1933, ele provou que se tal n existe, ele deve ser ímpar, sem quadrados e divisível por pelo menos pelo menos sete primos (ou seja, ω(n) ≥ 7). Em 1980, Cohen e Hagis provaram que n > 10²⁰ e que ω(n) ≥ 14. Além disso, Hagis mostrou que se 3 divide n então n > 10^1937042 e ω(n) ≥ 298848.

Conjectura de Carmichael

Isso afirma que não há número n com a propriedade que para todos os outros números m, m ≠ n, φ(m) ≠ φ(n). Veja o teorema de Ford acima.

Conforme afirmado no artigo principal, se houver um único contra-exemplo para esta conjectura, deve haver infinitos contra-exemplos, e o menor deles tem pelo menos dez bilhões de dígitos na base 10.

Hipótese de Riemann

A hipótese de Riemann é verdadeira se e somente se a desigualdade

${displaystyle {frac {n}{varphi (n)}}$

é verdadeiro para todos os n ≥ p₁₂₀₅₆₉# onde γ é a constante de Euler e p_120569# é o produto dos primeiros 120569 números primos.