Artigos

3.5: Teoremas de Fermat, Euler e Wilson - Matemática


Nesta seção, apresentamos três aplicações de congruências. O primeiro teorema é o teorema de Wilson, que afirma que ((p-1)! + 1 ) é divisível por (p ), para (p ) primo. A seguir, apresentamos o teorema de Fermat, também conhecido como pequeno teorema de Fermat, que afirma que (a ^ p ) e (a ) têm os mesmos restos quando divididos por (p ) onde (p nmid a ) . Finalmente, apresentamos o teorema de Euler, que é uma generalização do teorema de Fermat e afirma que para qualquer inteiro positivo (m ) que é relativamente primo a um inteiro (a ),

[a ^ { phi (m)} equiv 1 (mod m) ]

onde ( phi ) é a função ( phi ) de Euler. Começamos provando um teorema sobre o inverso de números primos de módulo inteiros.

Teorema

Seja (p ) um primo. Um inteiro positivo (m ) é seu próprio módulo inverso (p ) se e somente se (p ) divide (m + 1 ) ou (p ) divide (m-1 ).

Suponha que (m ) seja seu próprio inverso. Assim, [m.m equiv 1 (mod p). ] Portanto, (p mid m ^ 2-1 ). Como resultado,

[p mid (m-1) mbox {ou} p mid (m + 1). ] Obtemos isso (m equiv 1 (mod p) ) ou (m equiv -1 (mod p) ).

Por outro lado, suponha que

[m equiv 1 (mod p) mbox {ou} m equiv -1 (mod p). ]

Desse modo

[m ^ 2 equiv 1 (mod p). ]

Teorema de Wilson

Se (p ) é um número primo, então (p ) divide ((p-1)! + 1 ).

Quando (p = 2 ), a congruência se mantém. Agora vamos (p> 2 ). Usando o Teorema 26, vemos que para cada (1 leq m leq p ), há um inverso (1 leq bar {m} leq p ) tal que (m bar {m} equiv 1 (mod p) ). Assim, pelo Teorema 28, vemos que os únicos dois inteiros que têm seus próprios inversos são (1 ) e (p-1 ). Portanto, depois de acoplar os inteiros de 2 a (p-2 ) cada um com seu inverso, obtemos [2.3 ..... (p-2) equiv 1 (mod p). ] Assim, obtemos [1.2.3 ..... (p-2) (p-1) equiv (p-1) (mod p) ] Como resultado, temos ((p-1)! Equiv - 1 (mod p) ).

Observe também que o inverso do teorema de Wilson também é válido. O inverso nos diz se um inteiro é primo ou não.

Se (m ) é um número inteiro positivo com (m geq 2 ) tal que [(m-1)! + 1 equiv 0 (mod m) ] então (m ) é primo .

Suponha que (m ) tenha um divisor apropriado (c_1 ) e que [(m-1)! + 1 equiv 0 (mod m). ] Isso é (m = c_1c_2 ) onde (1

Apresentamos agora o Teorema de Fermat ou o que também é conhecido como Pequeno Teorema de Fermat. Ele afirma que o resto de (a ^ {p-1} ) quando dividido por um primo (p ) que não divide (a ) é 1. Em seguida, declaramos o teorema de Euler que afirma que o resto de (a ^ { phi (m)} ) quando dividido por um inteiro positivo (m ) que é relativamente primo a (a ) é 1. Provamos o Teorema de Euler apenas porque o Teorema de Fermat nada mais é do que um caso especial do Teorema de Euler. Isso se deve ao fato de que, para um número primo (p ), ( phi (p) = p-1 ).

Teorema de Euler

Se (m ) é um inteiro positivo e (a ) é um inteiro tal que ((a, m) = 1 ), então [a ^ { phi (m)} equiv 1 (mod m) ]

Observe que (3 ^ 4 = 81 equiv 1 (mod 5) ). Além disso, (2 ^ { phi (9)} = 2 ^ 6 = 64 equiv 1 (mod 9) ).

Apresentamos agora a prova do teorema de Euler.

Prova

Seja (k_1, k_2, ..., k _ { phi (m)} ) um módulo de sistema de resíduo reduzido (m ). Pelo Teorema 25, o conjunto [ {ak_1, ak_2, ..., ak _ { phi (m)} } ] também forma um módulo de sistema de resíduo reduzido (m ). Desse modo

[ak_1ak_2 ... ak _ { phi (m)} = a ^ { phi (m)} k_1k_2 ... k _ { phi (m)} equiv k_1k_2 ... k _ { phi (m)} (mod m). ]

Agora, uma vez que ((k_i, m) = 1 ) para todos (1 leq i leq phi (m) ), temos ((k_1k_2 ... k _ { phi (m)}, m ) = 1 ). Portanto, pelo Teorema 22, podemos cancelar o produto de (k ) 's em ambos os lados e obtemos

[a ^ { phi (m)} equiv 1 (mod m). ]

Uma consequência imediata do Teorema de Euler é:

Teorema de Fermat

Se p é primo e (a ) é um número inteiro positivo com (p nmid a ), então [a ^ {p-1} equiv 1 (mod p). ]

Apresentamos agora alguns teoremas que são consequências diretas do teorema de Fermat. O primeiro afirma o teorema de Fermat de uma maneira diferente. Diz que o resto de (a ^ {p} ) quando dividido por (p ) é o mesmo que o resto de (a ) quando dividido por (p ). O outro teorema determina o inverso de um módulo inteiro (a ) módulo (p ) onde (p nmid a ).

Se (p ) é um número primo e (a ) é um inteiro positivo, então (a ^ p equiv a (mod p) ).

Se (p nmid a ), pelo teorema de Fermat sabemos que [a ^ {p-1} equiv 1 (mod p). ] Assim, obtemos [a ^ {p} equiv a (mod p). ] Agora, se (p mid a ), temos

[a ^ p equiv a equiv 0 (mod p). ]

Se (p ) é um número primo e (a ) é um inteiro tal que (p nmid a ), então (a ^ {p-2} ) é o inverso de um módulo ( p ).

Se (p nmid a ), então o teorema de Fermat diz que [a ^ {p-1} equiv 1 (mod p). ] Portanto, [a ^ {p-2} a equiv 1 ( mod p). ] Como resultado, (a ^ {p-2} ) é o inverso de (a ) módulo (p ).

Exercícios

  1. Mostre que 10! +1 é divisível por 11.
  2. Qual é o resto quando 5! 25! é dividido por 31?
  3. Qual é o resto quando (5 ^ {100} ) é dividido por 7?
  4. Mostre que se (p ) é um primo ímpar, então (2 (p-3)! Equiv -1 (mod p) ).
  5. Encontre um módulo de sistema de resíduo reduzido (2 ^ m ), onde (m ) é um número inteiro positivo.
  6. Mostre que se (a_1, a_2, ..., a _ { phi (m)} ) é um módulo de sistema de resíduo reduzido (m ), onde (m ) é um número inteiro positivo com (m neq 2 ), então (a_1 + a_2 + ... + a _ { phi (m)} equiv 0 (mod m) ).
  7. Mostre que se (a ) é um inteiro tal que (a ) não é divisível por 3 ou tal que (a ) é divisível por 9, então (a ^ 7 equiv a (mod 63) ).

Fermat, Euler, Wilson - Três estudos de caso em teoria dos números

Nós relatamos em provas assistidas por computador de três teoremas da Teoria dos Números, viz. O Pequeno Teorema de Fermat, a generalização de Euler da declaração de Fermat e o Teorema de Wilson. Comum às provas formais é que a permutação de certas listas de números tem que ser comprovada, o que causa o principal esforço no desenvolvimento. Fazemos um breve levantamento do sistema usado neste experimento e ilustramos as provas antes de apresentá-las formalmente. Também discutimos soluções alternativas, relatamos o esforço necessário e concluímos com algumas experiências adquiridas com este experimento.

Esta é uma prévia do conteúdo da assinatura, acesso através de sua instituição.


Acrônimo para “A Verifier for Functional Programs”.

A base desta definição recursiva é dada por lemas sendo provados sem o uso de outros lemas.

Em quase todos os casos, o axioma de indução necessário para provar um lema ( ell ) é fornecido por um dos procedimentos usados ​​em ( ell ). No entanto, em casos raros, o usuário deve definir um procedimento adicional como ( mathfrak < mathfrak > ) para estipular um axioma de indução específico, seja porque isso é necessário ou (como no caso presente) facilita uma prova consideravelmente.

Infelizmente, não conseguimos ocultar completamente os componentes internos do sistema, pois existem 2 “truques” na formulação de lemas que suportam o raciocínio de igualdade automatizado, consulte a Seção. 2.1 para uma discussão.

(x ne 0 ) é exigido em (1), caso contrário (0 ^ <0> ) deve ser definido.

(< mathbb

> (p) ) denota que p é principal.

Aqui usamos notação matemática como ( sum nolimits _^ left (< beginn i-1 end> right) cdot x ^) em vez de (S (m + 1, n, 1, x) ) por uma questão de legibilidade.

O uso de (6) não é um “hack” para suportar o sistema, já que o lema (1) também possui uma prova automática. Mas é uma boa prática em matemática formular provas tão simples quanto possível, e este princípio se aplica ao raciocínio formal em particular (salvando um lema no presente caso).

Em vez de construtor indução com um caso de etapa ( forall n: < mathbb ,> varphi (n) rightarrow varphi (n + 1) ), usa destruidor indução com um caso de etapa ( forall n: < mathbb ,> n ne 0 wedge varphi (n-1) rightarrow varphi (n) ) já que o último é mais geral. Por exemplo, não há contrapartida construtiva para o esquema de indução obtido do procedimento ( mathfrak < mathfrak > ) da seção. 1

Como não fornece uma estrutura de dados definir, tivemos que usar listas em nossa prova formal. Se os conjuntos estivessem presentes, (purged ( ldots) ) teve que ser substituído por ( mathtt ) e ( approx ) por (= ) nos lemas, de modo que os lemas (25) e (31) se tornariam desnecessários. Isso significa que o uso de listas não complica a prova, pois apenas 1 interação do usuário para comprovar (25) e 2 interações do usuário para comprovar (31) poderiam ser salvas. Nas provas subsequentes das Seitas. 2.3 e 3, apenas o lema (31) se tornaria desnecessário, reduzindo ainda mais a economia.

O tempo refere-se a correr 3,5 abaixo Windows 7 Enterprise com CPU INTEL Core i7-2640M 2,80 GHz usando Java 1.8.0_45.

p ser primo não é apenas suficiente, mas também necessário para que a declaração seja considerada ((n-1)! , < textit> , n ne n-1 ) para todos os não primos (n ne 1 ). Veja [1] para uma prova assistida por computador.

Acontece que as classes de resíduos módulo a primo formam um campo, no entanto, este fato mais geral não é necessário aqui.

Mas podemos proibir a execução de chamadas de procedimento em um termo de caso ou em uma instância de um lema mediante o uso de Análise de Caso ou Use Lemma respectivamente. Também podemos usar o HPL-regra Normalização trabalhando como Simplificação, exceto que as chamadas de procedimento no goalterm não são executadas.

( subseteq ) denota a relação de subconjunto que não considera a ordem dos elementos da lista nem o número de ocorrências dos elementos ao comparar as listas. Por exemplo, ( left (3,2 right) subseteq left (2,2,3 right) ) e vice-versa.

Provas de ( sim ) 16.000 teoremas foram relatados em [5], onde ( sim ) 3800 foram provados por indução automatizada e ( sim ) 1000 por indução sugerida pelo usuário.

Para os estudos de caso na Tabela 1, a taxa de sucesso da heurística de indução / a participação de lemas prováveis ​​de primeira ordem varia de (93 , \% / 32 , \% ) na prova de Fermat usando o Princípio de Pigeon Hole para (97 , \% / 35 , \% ) ao usar o Teorema Binomial, e é 94–96% / 31–33 (\% ) para as provas restantes.

Veja, por exemplo a definição de primos e o invariante de loop exigido chamado prime1.basic em 2].


3.5: Teoremas de Fermat, Euler e Wilson - Matemática

jmc / 406.html, e foi atualizado pela última vez: 23/04/08

Título: Introdução à Teoria dos Números
Instrutor: Professor Joel M. Cohen

Escritório: Matemática 2313, Telefone: (301)405-5109
Telefone residencial: (202)546-1823.

Horário de aula: T-Th, 11: 00-12: 15
Localização: Matemática 0401
Endereço de e-mail: [email protected]
Livro: Teoria dos números elementares e suas aplicações, 5 / e, Kenneth H. Rosen, 2005, Addison-Wesley, ISBN 0-321-23707-2
Suplemento: Há algum material suplementar interessante em http://www.aw.com/rosen/resources.html.

Pré-requisito: MATEMÁTICA 141

Horário comercial: T-Th 1-2. Ocasionalmente, pode ser necessário alterar este horário, então me avise se você planeja me ver. Você também pode me enviar perguntas por e-mail. Vou responder às perguntas o mais rápido possível durante o horário de expediente e, se o tempo permitir, de outra forma.

Niveladora: Beth McLaughlin
Escritório: Matemática 2118
Endereço de e-mail: [email protected] .
Horário comercial: S-W: 1:00 - 1:55

TÓPICOS
Os inteiros
Divisibilidade
números primos
Maior divisor comum
Algoritmo euclidiano
Fatoração única
Congruências
Propriedades básicas
Aritmética modular
Função phi de Euler
Teoremas de Fermat, Euler e Wilson
Teorema do resto chinês
Funções Multiplicativas
Fórmula de inversão M & oumlbius
Número e soma de divisores
Raízes primitivas
Existência de raízes primitivas
Aritmética de índice
Resíduos Quadráticos
Símbolos de Legendre e Jacobi
Lei da reciprocidade quadrática
Possíveis Tópicos Adicionais
Equações Diofantinas Não Lineares
Números perfeitos, primos de Mersenne
Frações contínuas
Criptologia

Não serão realizados exames de maquiagem. Se você tiver uma ausência justificada para um exame, a nota será substituída por 1/2 da média das outras duas notas do exame. Se você fez os três exames, a nota mais baixa contará para a metade. Ausências justificadas serão concedidas apenas por razões médicas válidas, questões universitárias ou comparecimento em tribunal. Trabalhos de casa ou questionários dispensados ​​não serão usados ​​para calcular a nota final. Testes de maquiagem não serão dados. Quaisquer ausências não justificadas em questionários ou exames ou atrasos nos trabalhos de casa não justificados serão contados como 0, incluindo o exame final. Qualquer aluno com um motivo válido para ser dispensado de um exame deve entrar em contato comigo antes do exame, seja por e-mail ou por telefone, e apresente a documentação na próxima aula a que comparecer. Se você precisa ser desculpado por um Observância religiosa, você deve me avisar o mais rápido possível, mas em qualquer caso o mais tardar no final do período de ajuste do cronograma.

Trabalho de casa: A lição de casa será devido a cada dia. A lição de casa de cada dia será baseada no que foi abordado na aula do dia anterior. Se a tarefa não estiver clara, pergunte antes de sair da sala de aula! Os problemas do dever de casa estão listados abaixo. Os problemas solicitados serão discutidos em aula. Pode haver questionários ocasionais sobre problemas de dever de casa ou o equivalente.

Classificação: Um total de 500 pontos está disponível no curso:


Exames de três horas (100 pontos, menor contagem metade) 250

Lição de casa / questionários 100

Final 150

Total 500

Qualidade: A qualidade da apresentação das soluções será levada a sério neste curso na classificação dos testes e trabalhos de casa.

O cronograma provisório de exames é o seguinte:

Terça-feira, 4 de março Teste I
Quinta-feira, 17 de abril Teste II
Quinta-feira, 8 de maio Teste III
Quinta-feira, 15 de maio, das 8h às 10h
Final

Segue uma lista de problemas de lição de casa.

Seção 4.1: 6,14,20,27
Seção 4.2: 8,13,15
Seção 4.3: 4,8,12
Seção 4.4: 2,3,4

Seção 6.1: 9,16,24,33,34
Seção 6.3: 4,6,10,15

Seção 7.1: 6,8,19,37,39
Seção 7.2: 8,9,22, 30
Seção 7.3: 2,4,7
Seção 7.4: 3,4,5,12,14, 17

Seção 9.1: 4,6,9,16
Seção 9.2: 2,6,8,12
Seita 9.3: 4,5,9,14
Seita 9.4: 2,3,5,9

Seção 11.1: 1,2,5,9,10,11,20
Seção 11.2: 1,3,4, 15
Seita 11.3: 1,2,9,13

Sect. 13,1: 2,6,13,17
Sect. 13,2: 1,4,13
Sect. 13,3: 1,3,4

Seção 12.2: 1 (b, c, d, h), 4 (a, e, f), 6 (a, e, f), 8, 12
Seita 12.3: 1 (a, d), 3, 5,7

Sect. 8.1: 2,12,15
Sect. 8,2: 1,17
Sect. 8,3: 2
Sect. 8.4: 2,4


3.5: Teoremas de Fermat, Euler e Wilson - Matemática

Matemática 3527 (Teoria dos Números 1, Curso # 35849/35248), Primavera de 2020



Informação do curso
Instrutor Horários de aula Horário comercial
Evan Dummit
edummit no nordeste do ponto edu
A partir de quinta-feira, 12 de março, todas as reuniões presenciais no Nordeste são canceladas até novo aviso.
Em vez do horário comercial, o 3527 agora tem uma página da Piazza. Links para todo o material da palestra ao vivo estão hospedados lá.
Para obter informações detalhadas sobre o curso, consulte o Programa do Curso 3527 (Seção 01) (Seção 02). (Observação: qualquer informação dada em aula ou nesta página da web substitui o programa escrito.)
Todas as tarefas de casa serão postadas nesta página da web (veja abaixo).
As tarefas de casa agora devem ser enviadas através da página 3527 Blackboard .
Para enviar uma tarefa, navegue até "Tarefas" e selecione a tarefa de casa apropriada. Em seguida, anexe digitalizações de cada página de sua tarefa (ou um pdf) e clique em Enviar. Por favor, tente enviar as páginas em ordem.
As tarefas vencem às 18h Hora do Leste.
O instrutor escreverá notas de aula para o curso (veja abaixo) no lugar de um livro oficial à medida que o semestre avança. Em grau moderado, o curso seguirá a apresentação em J. Silverman, "Uma introdução amigável à teoria dos números", mas também adicionaremos material adicional substancial e não será necessário comprar o livro didático para este curso.

Os inteiros, axiomaticamente
1.2

Divisibilidade e Algoritmo Euclidiano
1.3

Primos e fatoração única
1.4

Congruências modulares e o módulo de inteiros m
2.2

Módulo de equações lineares m e o Teorema do Restante Chinês
2.3

Módulo de Poderes m: Ordens, Pequeno Teorema de Fermat, Teorema de Wilson, Teorema de Euler
2.4


Matemática 567 - Teoria Elementar dos Números

Horário comercial: Quartas-feiras, das 14h30 às 15h30, Van Vleck 605.

Niveladora: Yifan Peng, e-mail: [email protected]

Matemática 567 é um curso de teoria dos números elementares, destinado a alunos de graduação com especialização em matemática ou outras disciplinas quantitativas. Uma familiaridade geral com álgebra abstrata no nível de Matemática 541 será presumida, mas os alunos que não fizeram o 541 são bem-vindos se estiverem dispostos a se atualizar. Estaremos usando o novo (e barato) livro de William Stein Elementary Number Theory: Primes, Congruences, and Secrets, que enfatiza abordagens computacionais para o assunto. Se você não precisar de uma cópia física do livro, ele está disponível como um pdf legal gratuito. Estaremos usando o software matemático (de domínio público) SAGE, desenvolvido em grande parte por Stein, como um componente integral de nosso curso. Existe um tutorial online útil. Você pode baixar o SAGE para o seu computador ou usá-lo online.

Os tópicos incluem alguns subconjuntos de, mas não estão limitados a: Divisibilidade, o algoritmo euclidiano e o GCD, equações diofantinas lineares, números primos e exclusividade de fatoração. Congruências, teorema do resto chinês, "pequeno" teorema de Fermat, teorema de Wilson, teorema de Euler e função totiente, o criptosistema RSA, esquema de criptografia de Rabin, protocolo de troca de chaves Diffie-Hellman. Funções numéricas, funções multiplicativas, inversão de Möbius. Raízes e índices primitivos. Reciprocidade quadrática e o símbolo de Legendre. Números perfeitos, primos de Mersenne, primos de Fermat. Triplos pitagóricos, casos especiais do "último" teorema de Fermat. Números de Fibonacci. Frações contínuas. Distribuição de primos, discussão do teorema dos números primos. Teste de primazia e algoritmos de fatoração.

Políticas do curso: O dever de casa será entregue às sextas-feiras. Pode ser entregue tarde apenas com avançar permissão do seu avaliador. É aceitável o uso de calculadoras e computadores nas tarefas de casa (na verdade, alguns deles exigirão um computador), mas calculadoras não são permitidas durante os exames. Encorajamos vocês a trabalharem juntos na lição de casa, mas as redações devem ser feitas individualmente.

Muitos dos problemas neste curso exigirão que você prove coisas. Espero que as provas sejam escritas em sentenças em inglês; as provas do livro de Stein são um bom modelo para o nível de verbosidade que procuro.

Classificação: A nota em Matemática 567 será composta por 50% de trabalhos de casa, 25% de meio do semestre e 25% final. A prova será no dia 11 de março, em sala de aula. O exame final será no dia 08/05/2020, das 7h45 às 9h45 na sala TBA.

Programa de Estudos: (Isso pode mudar à medida que vemos que ritmo funciona bem para o curso. Todos os números de seção referem-se ao livro de Stein.)

  • 22 a 31 de janeiro: números primos, fatorações primos, algoritmo euclidiano e GCD (1,1-1,2)
  • 3 a 7 de fevereiro: o mod n de inteiros, o teorema de Euler, a função phi (2.1-2.2)
  • 10 a 14 de fevereiro: exponenciação modular, teste de primalidade e raízes primitivas (2,4-2,5)
  • 17 a 21 de fevereiro: criptografia de chave pública e RSA (3.1-3.4)
  • 24 a 28 de fevereiro: algoritmo de Rabin (não consta do livro), números algébricos
  • 2 a 6 de março: Reciprocidade quadrática (4.1-4.4)
  • 9 de março, 13 de março: frações contínuas finitas e infinitas (5.1-5.3)
  • 11 de março: Exame intermediário
  • 23-30 março: Frações contínuas e aproximação diofantina (5,4-5,5)
  • 1-3 de abril: Equações diofantinas I: equação de Pell e teorema de Lagrange
  • 6 a 10 de abril: Mais equações diofantinas, curvas elípticas (6.1)
  • 13 a 17 de abril: Aplicações de curvas elípticas (6.2-6.3)
  • 20-24 abril: Mais aplicações de curvas elípticas (6.4)
  • 27 de abril a 1 de maio: tópico avançado a ser definido: talvez uma discussão adicional sobre técnicas criptográficas?

Aulas em vídeo: Como a universidade está sendo transferida para o ensino apenas online, as palestras após as férias de primavera deverão ser ministradas online. Vou postar aqui vídeos para vocês assistirem para o material que precisamos cobrir. Por favor, assista a eles e me dê feedback sobre como eles podem ser melhorados.

  • Palestra para 23 de março: assista aqui.
  • Palestra para 25 de março: assista aqui.
  • Palestra para 27 de março: assista aqui.
  • Palestra para 30 de março: assista aqui.
  • Palestra para 1º de abril: assista aqui.
  • Palestra para 3 de abril: assista aqui.
  • Palestra para 6 de abril: assista aqui.
  • Palestra para 8 de abril: assista aqui.
  • Palestra para 10 de abril: assista aqui.
  • Palestra para 13 de abril: assista aqui.
  • Palestra para 15 de abril: assista aqui.
  • Palestra para 17 de abril: assista aqui.
  • Resumo da palestra de 20 de abril: assista aqui.

Trabalho de casa: O dever de casa deve ser entregue no início da aula na sexta-feira especificada. Digitar seu dever de casa não é um requisito, mas se você ainda não conhece LaTeX, eu recomendo que você o aprenda e use para escrever seu dever de casa. Às vezes, atribuirei problemas extras, que enviarei por e-mail para a lista de turmas e incluirei aqui.

Problema A: Use SAGE para calcular o número de x em [1..N] de modo que x ^ 2 + 1 seja primo, para N = 100, N = 1000 e N = 10000. Seja f (N) o número de tal x.

a) Você pode formular uma conjectura sobre a relação entre f (N) e N / log N?

b) E se x ^ 2 + 1 for substituído por x ^ 2 + 2? Você pode explicar por que x ^ 2 + 2 parece menos provável de ser primo? (Dica: considere x mod 3.)

c) Prove que f (N) é no máximo (1/2) N + 1. (Dica: considere x mod 2.)

d) Dê o melhor limite superior possível para f (N).

Observe que, apesar das regularidades evidentes que você observará neste problema, nem mesmo sabemos se existem infinitos primos da forma x ^ 2 + 1! Você se tornaria muito famoso se provasse isso.

  • 7 de fevereiro: 2.6 (a formulação da evidência numérica deve ser feita pelo Sage, se você tiver o Sage funcionando, e pela calculadora, se não, você pode usar uma ferramenta online como esta para testar se um número é primo.) 2.8,2.9,2.11,2.12 , 2.14,2.19
  • 17 de fevereiro: 2.15, 2.18, 2.23, 2.26, 2.30.

Problema A: Prove que se n = pq, com p, q primo, então n não é um número de Carmichael.

Problema A. Prove que existem infinitos primos p tais que 2 é não uma raiz primitiva em Z / pZ. Nós dividimos isso em etapas.

Problema A.1. Prove que, se x é um elemento de Z / nZ, então x ^ 2 não é uma raiz primitiva.

Problema A.2. Prove que existem infinitos primos p tais que 2 é um quadrado em Z / pZ. Dica: suponha que haja apenas um número finito de primos p_1, .. p_r, e defina N = (p_1 .. p_r) ^ 2 - 2. Para onde você pode ir a partir daqui.

Problema A.3. Dê uma lista de cinco primos p tal que 2 não seja uma raiz primitiva em Z / pZ (você pode usar o método desta prova ou qualquer outro).

Problema B. Prove que 24 é o maior inteiro n tal que cada elemento de (Z / nZ) ^ * é uma raiz de x ^ 2-1.

  • 28 de fevereiro: Problema A. Usando p = 23 eq = 31, mostre como criptografar a mensagem x = 240 com o algoritmo de Rabin. Encontre todas as descriptografias possíveis de sua mensagem criptografada.
  • 23 de março: 4.1 do livro.

Problema A. Dê uma fatoração primária do inteiro gaussiano 7 + 9i.

Problema B. Leia as notas a partir daqui. Observe que Z [i] satisfaz um teorema da redução: se n e d são inteiros gaussianos, então existem inteiros q e r tais que n = qd + r e Norm (r) & lt Norm (d). Mas (em contraste com o caso de Z) este d pode não ser único. Em alguns contextos, é melhor poder escolher r exclusivamente, mesmo que isso signifique deixar r ter norma maior que Norm (d).

B.1. Quando d = 1 + 2i, mostre que, para cada n em Z [i], há um único par (q, r) em Z [i] tal que n = qd + r e r está contido no conjunto <0,1,2,3,4>. Por exemplo, i pode ser escrito como i (1 + 2i) + 2, então dizemos que i se reduz a 2 mod (1 + 2i). (Dica: suponha que q (1 + 2i) + r = q '(1 + 2i) + r'. O que podemos dizer sobre (r-r '), e por que isso é incompatível com r e r' estar em < 0,1,2,3,4>?

B.2. Mostre que se n for um inteiro em Z, a redução de n mod (1 + 2i) é igual ao seu mod 5 de redução.

Problema C. Vamos tentar descobrir como definir "phi (d)" para um inteiro gaussiano d. Suponha que S é um conjunto de inteiros gaussianos tais que todo n em Z [i] pode ser escrito exclusivamente como qd + r, com q em Z [i] e r em S. (Por exemplo, quando d = 1 + 2i, nós mostrado no problema B que podemos considerar S como sendo <0, 4>. Também seria normal considerar S como <1 .. 5> ou <0, i, 2i, 1 + i, 1 + 2i>. Na verdade, acontece que S tem que ser um conjunto de tamanho Norm (d) (posso ou não provar isso em sala de aula, se não, sinta-se à vontade para aceitá-lo.)

Agora defina phi (d) como o número de elementos s de S tal que s e d são coprimos.

C.1. Calcule phi (1 + 2i) e phi (3).

C.2. Prove que o valor de phi (d) não depende da escolha de S.

C.3. Prove que todo n em Z [i] que é coprime de 3 satisfaz n ^ phi (3) = 1 mod 3, ou seja, o teorema de Euler é válido neste caso. (Você pode provar isso por cálculo direto, é claro, se quiser, pode provar que o teorema de Euler é válido para Z [i] em geral, adaptando a prova do livro de Stein ou a que demos em aula.)

Problema A. Expresse 50005 como a soma de dois quadrados.

Nos próximos dois problemas denotamos por r (n) o número de maneiras de expressar n como a soma de dois quadrados (ou seja, o número de pares ordenados (a, b) tal que a ^ 2 + b ^ 2 = n.) Por exemplo, r (5) = 8: (a, b) = (+/- 1, +/- 2) ou (+/- 2, +/- 1).

Problema B. Prove que, para qualquer N, existe um inteiro n tal que r (n) & gt N. (I.E., a função r (n) é ilimitado.)

Problema C. Se você gosta do Sage, escreva um programa curto no Sage para calcular r (n) e calcular a média de r (n) como n varia de 1 a 1000. Quer goste ou não do Sage, adivinhe como essa média se comportaria se você substituísse "1000" por um número cada vez maior. (Sinta-se à vontade para perguntar aos amantes do Sábio qual resposta eles obtiveram na primeira parte opcional da pergunta.) Você pode provar que essa suposição está correta?

Problema D. Vimos na aula que o anel Z [sqrt (-5)] não tem fatoração única 6 pode ser fatorado como 2 * 3 ou (1 + sqrt (-5)) (1-sqrt (-5) ) Neste problema, vamos provar que Z [sqrt (-d)] não tem fatoração única para CADA ímpar d & gt = 5. (Na verdade, é verdade para todos d & gt = 5, mas para tornar a prova gerenciável, restringiremos a o caso estranho.]

D.1. Mostre que (1 + sqrt (-d)), (1-sqrt (-d)) e 2 são irredutíveis em Z [sqrt (-d)].

D.2. Agora forneça um elemento de Z [sqrt (-d)] que tem duas fatorações distintas em irredutíveis. (Dica: imite o exemplo que usamos para Z [sqrt (-5)].) Observação: Os anéis Z [sqrt (d)], onde d é positivo, são bastante diferentes - aqui acreditamos que existem infinitos muitos com fatoração única, embora essa conjectura não tenha sido comprovada por muitas décadas!

Problema A: Discutimos em aula o problema de estudar quais inteiros positivos são a soma de dois quadrados. Neste problema, provamos que cada elemento n de (Z / pZ) é a soma de dois quadrados. Nós argumentamos da seguinte forma. Seja S o conjunto de quadrados em (Z / pZ), e seja T o conjunto de (Z / pZ) que consiste em todos os elementos da forma n - x ^ 2, para algum x em (Z / pZ).

A.1. Qual é o tamanho de S e de T? Use isso para mostrar que S e T não são disjuntos.

A.2. Dado que S e T não são disjuntos, prove que n é a soma de dois quadrados.

Problema B. Usando a expansão de fração contínua, encontre uma solução para a equação de Pell x ^ 2 - 13 y ^ 2 = 1.

Problema C. Mostre que a equação de Pell modificada x ^ 2 - 7y ^ 2 = -1 não tem soluções em inteiros x, y. (Dica: reduza o módulo da equação para um número primo adequadamente escolhido.)

Problema D. Stuffy Stirnweiss terminou a temporada de 1945 com uma média de rebatidas de 0,3085443. Usando frações contínuas, adivinhe quantas tentativas ele tinha. Tony Cuccinello teve uma média de rebatidas de 0,3084577. Dado que ele teve mais de 200 e menos de 600 rebatidas, você pode estimar o número de rebatidas que ele teve?

Problemas do livro 6.1, 6.2, 6.5, 6.10.

Problema A.1. Escolha dois valores de a em F_11 = Z / 11Z (a não igual a 3), de modo que a equação y ^ 2 = x ^ 3 + ax + 1 defina uma curva elíptica (ou seja, é suave). Para cada um, determine o número de pontos #E (F_11) e verifique se ele se enquadra no intervalo descrito na aula.

Problema A.2. O ponto P = (0,1) encontra-se em cada uma dessas curvas. Para a = 3 determine a ordem de P no grupo da curva elíptica, ou seja, encontre o menor inteiro positivo n tal que nP = (infinito) - o elemento de identidade na lei do grupo.

Problema B. Mostre que se A + Bi é o cubo de um inteiro gaussiano, então A ^ 2 + B ^ 2 é um cubo perfeito.


3.5: Teoremas de Fermat, Euler e Wilson - Matemática

O trabalho de Euler na Teoria dos Números

Jodi Dunkelman
História da Matemática
Rutgers, Primavera de 2000

Leonhard Euler fez muitas contribuições para o campo da matemática, incluindo seu trabalho na teoria dos números. Este matemático suíço passou a maior parte de sua vida profissional na Rússia, onde seu trabalho teórico dos números foi sugerido por questões levantadas por Pierre de Fermat, bem como por suas próprias ideias. O trabalho de Euler na teoria dos números incluiu tópicos como o estudo de números perfeitos, a lei da reciprocidade quadrática, a chamada equação de Pell e o Último Teorema de Fermat, para citar apenas alguns. Embora Euler não tenha iniciado o estudo de muitos dos problemas em que trabalhou, nem os resolveu completamente, ele fez grandes contribuições para si mesmo e para muitos outros matemáticos. Leonhard Euler nasceu em 15 de abril de 1707, em Basel, Suíça, e morreu em 18 de setembro de 1783, em São Petersburgo, Rússia. Tendo crescido em Riehen, uma cidade não muito longe de Basel, Euler aprendeu matemática com seu pai porque não era ensinada na escola que ele frequentava. Johann Bernoulli havia descoberto o talento matemático com que o jovem Euler foi abençoado. Em 1725, com apenas 18 anos, Euler já estava estudando na Universidade de Basel e, no ano seguinte, estava concluindo seus estudos de graduação lá. No outono de 1726, Euler recebeu uma oferta de um cargo na Academia Russa de Ciências em São Petersburgo. Pode parecer um pouco estranho que uma academia estrangeira tão distinta soubesse do jovem Euler na Suíça, mas quando os filhos de Bernoulli, Nicolau II e Daniel, foram aceitos em 1725, eles fizeram um acordo entre si que sempre que uma vaga seria venha, Euler seria o primeiro que eles recomendariam. Como resultado, Euler chegou a São Petersburgo em 17 de maio de 1727, quando tinha apenas 20 anos (Calinger 124-5). É nesse período que a maior parte de seu trabalho na teoria dos números foi realizada.

A teoria dos números é definida na Encarta Encyclopedia como "um ramo da matemática que lida com as propriedades e relações dos números. A teoria dos números inclui muito da matemática, especialmente a análise matemática. Geralmente, a teoria dos números está confinada ao estudo de inteiros, ou ocasionalmente a algum outro conjunto de números com propriedades semelhantes aos inteiros. " A teoria dos números contém ideias muito básicas, mas também pode ser difícil de provar e compreender. Existem problemas que podem ser escritos facilmente, mas cujas respostas ainda surpreendem os matemáticos mais ilustres. Em suma, a teoria dos números tem sido de interesse para os matemáticos desde que os números foram inicialmente considerados curiosos (Minério 25).

Em 1 de dezembro de 1729, o secretário da conferência Christian Goldbach perguntou pela primeira vez a Euler, em uma carta, se ele sabia da conjectura de Fermat (Calinger 130, Inverno 10). Isso se refere à declaração de Fermat de que a equação xn + yn = zn não tem solução para inteiros x, y e z diferentes de zero, quando n> = 3 (minério 204). Euler mais tarde provou isso para n = 3 em seus Elementos de Álgebra, veja a prova anexa (Euler 449-50) (omitido no original) . Esta prova explora um bom entendimento das propriedades dos números da forma a 2 + 3b 2 2 e, portanto, não há razão para acreditar que Fermat também não tenha provado seu teorema para n = 3 (Burton 490). Em uma nota famosa de Fermat, ele escreveu: "Dividir um cubo em dois outros cubos, uma quarta potência, ou em qualquer potência geral, em duas potências da mesma denominação acima da segunda é impossível, e eu certamente encontrei um admirável prova disso, mas a margem é muito estreita para contê-lo "(Smith SB 213). Isso me faz pensar se Euler foi realmente o primeiro a resolver um caso importante do Último Teorema de Fermat.

Outra das ideias de Fermat que Euler trabalhou veio a ser conhecida, por erro do próprio Euler, como Equação de Pell. Pell's equation is y 2 - Ax 2 = 1, where A is any non-square integer. This problem was first proposed Fermat as a challenge to English mathem aticians Lord Brouncker and John Wallis (Smith SB 214). Euler got the impression from Wallis that Pell was given the acknowledgement of finding the method to solve this problem, and after he had become aware of his mistake in 1730, at the age of 23, and then included it in his Introduction to Algebra that was written in 1770 (Edwards 33). Euler probably got confused because "Pell's name occurs frequently in Wallis's Algebra, but never in connection with the equation x 2 - Ny 2 = 1 . since its traditional designation as `Pell's equation' is unambiguous and convenient, we will go on using it, even though it is historically wrong" (Weil 174).

  1. The n th perfect number P n contains exactly n digits.
  2. The even perfect numbers end alternately in the digits 6 or 8.

These conjectures were proven wrong when the 5th perfect number was correctly given in an anonymous 15th Century manuscript as P 5 = 33,550,336, which obviously does not have 5 digits, so the first conjecture can now be discarded. The second conjecture was refuted when the sixth perfect number P 6 = 8,589,869,056 was seen to end in a 6, rather than an 8 (Burton 474-5).

Although Euclid's Elements dealt mainly with geometry, it was Euclid in Book IX, Proposition 36, who proved that if the sum 1 + 2 + 2 2 + 2 3 + . + 2 (k-1) = p is a prime number, then 2 (k-1) p is a perfect number (Burton 475, Euclid). Euler then made a claim about the occurrence of perfect numbers, he stated "I venture to assert that aside from the cases noted [Euler earlier mentioned 11, 23, 29, 37, 43, 73, 83], every prime less than 50, and indeed than 100, makes 2 (n-1) * (2 n ) -1 a perfect number, whence the eleven values 1, 2, 3, 5, 7, 13, 17, 19, 31, 41 , 47 of n yield perfect numbers" (Burton 480).

Although Euler was wrong, he had found his own mistakes with n = 41 and n = 47 , and corrected them in 1753 (Ore 93). In 1732 Euler also discovered the 8th perfect number, which is 2 30 * (2 31 -1) = 2,305,843,008,139,952,128, also know as the Mersenne prime M31 (Ore 93, Barlow). Thus perfect numbers have been a topic of interest for many years to this day, no mathematician has been able to determine whether there are finitely or infinitely many perfect numbers. Mathematicians make empirical conjectures that they believe to be true, but through counterexamples may find them to be false. Burton remarks, "Part of the problem is that in contrast with the single formula for generating perfect numbers (even), there is no known rule for finding all amicable pairs of numbers (Burton 483).

  1. Given an integer N , describe the primes p = 2 for which p = x 2 + Ny 2 is solvable with integers x and y
  2. Given an integer N , describe the primes p = 2 for which p divides m (p|m) , where m is any integer of the form m = x 2 + Ny 2 , with integers x and y

Another explanation of the law of quadratic reciprocity is given as follows:
"If p and q are two positive odd primes, at least one of which has the form 4n + 1 , then q is a quadratic residue or nonresidue of p according as p is a quadratic residue or nonresidue of q . But if both the primes p and q have the form 4n + 3 , q is a quadratic residue or nonresidue of p according as p is a quadratic nonresidue or residue of q " (Dirichlet 66).

As one example of this take p =3 , q = 5 then p is a quadratic nonresidue of q and at the same time q is a quadratic nonresidue of p . (Dirichlet 66).

These are only a select few of Euler's accomplishments in number theory. He made other contributions to number theory, as well as to other branches of pure and applied mathematics. His end, as quoted by Yushkevich, came as follows. "On September 18, 1783, Euler spent the first half of the day as usual. He gave a mathematics lesson to one of his grandchildren, did some calculations with chalk on two boards on the motion of balloons then discussed with Lexell and Fuss the recently d iscovered planet Uranus. About five o' clock in the afternoon he suffered a brain haemorrhage and uttered only 'I am dying' before he lost consciousness. He died about eleven o'clock in the evening."

This is how Euler based his life around mathematics - each day to the fullest!


3010tangents

So you think you’re a math whiz. You storm into parties armed with math’s most flamboyant tricks. You can recite the digits of π and e to 50 digits—whether in base 10 or 12. You can calculate squares with ease, since you’ve mastered the difference of squares x 2 – y 2 = (x + y)(x – y). In tackling 57 2 , simply notice that 57 2 – 7 2 = (57 + 7)(57 – 7) = 64*50 = 3200. Adding 7 2 to both sides gives 57 2 = 3249.


Image by Hashir Milhan from
Wikimedia Commons under
Creative Commons.

You can also approximate square roots using the truncated Taylor series √x ≈ c + (x – c 2 )/(2c) where c 2 is the closest perfect square less than or equal to x. So √17 ≈ 4 + (17 – 16)/(2*4) = 4.125, whereas √17 = 4.123105 . . ..

But do you know what number theory is? It’s not taught in high school, and everyone’s repertoire of math tricks needs some number theory. Mastering modular arithmetic—the first step in number theory—will make you the life of the party. Calculating 83 mod 7 just means find the remainder after dividing by 7: 83 = 11*7 + 6, so 83 ≡ 6 mod 7. But it’s actually easier since 83 = 7*12 + (-1), so 83 ≡ -1 ≡ 6 mod 7. Modular arithmetic reveals the secrets of divisibility. Everybody knows the trick to see whether 3 divides a number you just add the digits and check if 3 divides that number. But the reasoning is obvious when you write m = 10 n uman + 10 n -1 uman-1 + . . . + 10uma1 + uma0 where the umaeu are the digits of m. Each 10 k has a remainder of 1 modulo 3 so muman + uman-1 + . . . + uma1 + uma0 mod 3. Using this method generates tricks for other integers.

For instance, if 13 divides m, then 13 divides uma0 – 3uma1 – 4uma2uma3 + 3uma4 + 4uma5 + a6 – 3uma7 – 4uma8 + . . . and the pattern continues. This is because

10 2 ≡ 10*10 ≡ (-3)(-3) ≡ 9 ≡ -4 mod 13,

10 3 ≡ 10 2 *10 ≡ (-4)(-3) ≡ 12 ≡ -1 mod 13,

10 4 ≡ 10 3 *10 ≡ (-1)*(-3) ≡ 3 mod 13,

10 5 ≡ 10 4 *10 ≡ 3*(-3) ≡ -9 ≡ 4 mod 13,

and 10 6 ≡ 10 5 *10 ≡ 4*(-3) ≡ -12 ≡ 1 mod 13.

From 10 6 and onwards the pattern repeats. In fact, calculating 10 n mod k for successive n will reveal the divisibility rule for k.

Then comes Fermat’s little theorem, the key to solving seemingly impossible calculations.


Fermat. Image from Wikimedia
Commons. Under public domain.

The theorem states for a prime p and integer uma that a puma mod p. If p doesn’t divide a, then a p -1 ≡ 1 mod p. I’ll illustrate the power of this little result in a computation. Let’s find 2 371 mod 5. We’ll be using 2 4 ≡ 1 mod 5, which we get from Fermat’s little theorem. Now 2 371 = 2 368 2 3 =(2 4 ) 92 2 3 , so by the theorem, 2 371 = (2 4 ) 92 2 3 ≡ 1 92 2 3 ≡ 1*2 3 ≡ 8 ≡ 3 mod 5. Exploiting Fermat’s little theorem can impress your friends, but try to avoid questions. Computing residues modulo a composite number—calculating b mod n for a composite number n—may require paper and ruin the magic.

Leonhard Euler proved a more general version of Fermat’s little theorem it’s called the Euler-Fermat theorem. This theorem isn’t for parties explaining it to the non-mathematically inclined will always require paper and some time. Nonetheless, it will impress at dinner if you have a napkin and pen.

Understanding this theorem requires Euler’s totient function φ(n).


Euler. From Wikimedia
Commons. Under public domain.

The number φ(n) for some n is the number of positive integers coprime with n that are less than or equal to n. Two numbers uma e b are coprime if their greatest common factor is one. Hence 14 and 3 are coprime because their biggest shared factor is 1, but 21 and 14 aren’t coprime because they have a common divisor of 7. Moreover, φ(14) = 6 because 14 has six numbers less than or equal to it that are coprime with it: 1, 3, 5, 9, 11, and 13. Notice that if p is prime, φ(p) = p – 1 because every number less than p is coprime with p.

Now the Euler-Fermat theorem states that uma φ ( n ) ≡ 1 mod n, which looks similar to uma p -1 ≡ 1 mod p for a prime p. In fact, if n = φ(p) = p – 1 for a prime p, the theorem reduces to Fermat’s little theorem.

Fermat’s little theorem has another generalization, Lagrange’s theorem. Joseph-Louis Lagrange was Euler’s student. Lagrange’s theorem generalizes both the previous theorems and doesn’t even require numbers. But due to the required background in group theory, I won’t go over the theorem. You can find links to more information on Lagrange’s theorem below.

Remember, a math whiz doesn’t need props like a magician does. Hook your audience with some modular arithmetic, and reel the people in with Fermat’s little theorem. If you want to get complicated, the most you’ll need is a pen and some paper.

Lagrange’s theorem (only for the brave): http://cims.nyu.edu/

Number theory textbooks: Gordan Savin’s Numbers, Groups, and Cryptography and George E. Andrews’s Number Theory

Interesting sources of math tricks and problems: Paul Zeitz’s O Art, Craft of Problem Solving e The USSR Olympiad Problem Book, e What is Mathematics by Richard Courant and Herbert Robbins


Number Theory: In Context and Interactive

Let's start by talking about (x^3=y^2+2) as a type of curve. Recall from Example 3.5.3 that Bachet de Méziriac first asserted this had one positive integer solution in 1621, very early in the development of modern number theory.

Example 15.3.1 .

What is that solution? (Even if you don't remember, you should be able to find it quickly.)

Fermat, Wallis, and Euler also studied this equation and gave various discussions and proofs of the uniqueness of its solution. As we first saw in Section 3.5, this equation is actually one of a more general class of equations called the Mordell equation:

Remark 15.3.2 .

Louis Mordell was an early 20th-century American-born British mathematician. He proved some remarkable theorems about this class of equations. We have already seen that these are nontrivial, and that some have no solution (Proposition 7.6.3, or see below Fact 15.3.3). Even deciding whether there are no solutions or not turns out to be quite tricky Helmut Richter has a somewhat old website with some tables of what é known about integer solutions.

Notice that Mordell's set of curves are not quadratic/conic, but rather a set of cubic curves. Actually, as mentioned before, they are examples of a special type of elliptic curves, which makes them more mysterious (and, as it happens, more useful for cryptography – we allude to this briefly in Subsection 11.5.1).

One of Mordell's remarkable theorems states that, for a given (k ext<,>) the equation can only have finitely many integer points (in fact, there are even useful bounds for how many that depend only on the prime factorization of (k)). At the same time, Mordell curves are apparently “simple” enough that they can still have infinitely many racional points (see Theorem 15.3.6). Gerd Faltings won a Fields Medal for proving that higher-degree curves cannot have infinitely many rational points. If you are online, see which points you can find in the interact below.

Subsection 15.3.1 Verifying points don't exist

Proving things about Mordell's equation is quite tricky, but once in a while there is something you can do. For instance, we can verify something we can see in the interact above.

Fact 15.3.3 .

There are no integer solutions to (x^3=y^2-7 ext<.>)

Prova.

Recall that we nearly finished the proof of this in Proposition 7.6.3! We had reduced to showing that

was impossible if no prime of the form (p=4n+3) could divide (y^2+1 ext<.>)

This is not possible, because Fact 13.3.2 implies there are no square roots of (-1) modulo (p) for this type of (p ext<.>)

Fact 15.3.3 is a simple version of the following far more general statement.

Theorem 15.3.4 .

all prime divisors (p) of (N) are of the form (4k+1 ext<.>)

Then there is no solution to

Prova.

The proof basically follows the same outline as Proposition 7.6.3 with Fact 15.3.3. See Exercise 15.7.8.

One can prove lots of similar statements using only congruence considerations. The previous theorem is [C.4.9, Theorem 14.1.2], and that text has several other interesting variants. See Conrad's notes and [C.2.8, Theorem 7.4C.1] for even more special cases. See Subsection 17.5.4 for some other examples (without proof) of how knowing when square roots exist helps solve Mordell equations.

But there is a larger point to make, based on the very specific conditions on (M) and (N ext<.>) Namely, if we want to prove anything about such equations with methods we currently have access to in this text, we have no hope of getting any interesting general results.

Subsection 15.3.2 More on Mordell

Let's see what I mean by “no hope” here by returning to Bachet's original equation, (x^3=y^2+2 ext<.>) What are some naive things we can say?

It should be clear that (x) and (y) must have the same parity.

If they are both even then (x^3) is divisible by 4, but (y^2+2equiv 2 ext< (mod >4) ext<,>) which is impossible.

That doesn't really narrow things down much.

Now, Euler nearly proves the following fact.

Fact 15.3.5 .

The only positive solution to the Bachet equation is (x=3,y=5 ext<.>)

Prova.

Proving this is already a little sophisticated, and is closely connected to the use of complex numbers in Section 14.1. Here we will give the idea behind Euler's ‘proof’.

In examining (a^2+b^2 ext<,>) we factored it as ((a+bi)(a-bi)) using a square root of negative 1 (relative to (mathbb)). Similarly, we would like to factor the (x^2+2 ext<.>) But it can't be done in (mathbb[i] ext<.>)

Instead, we could try to use the square root of (-2 ext<,>) and define

We haven't done anything with cubes yet …

Here is the tricky bit. In the integers, if (x^3=pq) and (gcd(p,q)=1 ext<,>) then (p) and (q) must both be perfect (integer) cubes. So Euler assumes this works in (mathbb[sqrt<-2>]) as well, and that the factors of (y^2+2) are “coprime” (whatever that means in this new number system). (A very nice discussion of this is in [C.4.14], including a full proof in its appendix.)

Then some basic algebraic manipulation of

and divisibility considerations end up showing that (b mid 1) and (a=pm b ext<,>) which ends up implying (y=pm 5) and (x=3 ext<.>) (We will not take this further see Exercise 15.7.10.)

Where's the problem? It turns out you can say that if a product of coprime numbers is a cube, then the factors are cubes in this situation however, it requires some (geometrically motivated) proof, just like with (mathbb[i] ext<.>) In his 1765 “Vollständige Anleitung zur Algebra”, sections 187-188 and 191, Euler explicitly says that this just works – in any number system with (mathbb[sqrt] ext<.>) He solves the original Bachet equation in section 193, and solves (y^2+4=x^3) using the same technique in section 192, without realizing he had not proved this implicit assumption. (This is the same assumption he tacitly made in examining Fermat's Last Theorem for the case (n=3 ext<.>))

But we shouldn't be too hard on Euler! He was one of the first people to even consider some essentially random new number system obtained by adjoining (sqrt) (for some integer (c)) to the integers. And as noted in Example 3.5.4, in 1738 he gave a correct and full proof of the observation that (8) and (9) is the only time a perfect square is preceded by a perfect cube, which is Mordell's equation for (k=-1 ext<.>) (See also Question 3.5.5.)

If you are interested in more information about how to prove cases of Mordell's equation, there are many good resources, including a nice one on Keith Conrad's website. But even finding a bound on the Tamanho of solutions to Mordell's equation for a given (k) is tricky.

Mordell, Siegel, and Thue all had a part after World War I in showing there are finitely many solutions for a given (k ext<,>) but said nothing about how big (x) and (y) might be.

An early bound on the size of the numbers was that

which is of course ridiculously huge.

More recent conjectures are that (x) has absolute value less than (e^C |k|^<2+epsilon> ext<,>) where (epsilon) is as small as you want and (C) seems to pretty close to one, probably less than two.

We cannot close discussion of this topic without a final very famous result carrying Mordell's name. Recall that these curves can have infinitely many racional points, even if they have finitely many (or zero) integer points. The following is a bit of a surprise, then the rational points can still be described finitely.

Theorem 15.3.6 . Mordell's Theorem.

Essentially, the set of (rational) points on a Mordell curve is a combination of finitely many “cyclic” (recall Fact 14.2.7) groups (in a very specific way I will not describe), and so it can be described using finitely many of the rational points.

If you like, the number of rational points might be infinite, but not too infinite.


Math 567 -- Elementary Number Theory Ellenberg

Professor: Jordan Ellenberg ([email protected]) Office Hours: Weds, 2:30-3:30, Van Vleck 323.

Grader: Silas Johnson ([email protected]) Office Hours: Thurs, 1:15-2:15, Van Vleck 522. Silas's page, with problem set solutions.

Math 567 is a course in elementary number theory, aimed at undergraduates majoring in math or other quantitative disciplines. A general familiarity with abstract algebra at the level of Math 541 will be assumed, but students who haven't taken 541 are welcome to attend if they're willing to play a little catchup. We will be using William Stein's new (and cheap) textbook Elementary Number Theory: Primes, Congruences, and Secrets, which emphasizes computational approaches to the subject. If you don't need a physical copy of the book, it is available as a free legal .pdf. We will be using the (free, public-domain) mathematical software SAGE, developed largely by Stein, as an integral component of our coursework. There is a useful online tutorial. You can download SAGE to your own computer or use it online.

Topics include some subset of, but are not limited to: Divisibility, the Euclidean algorithm and the GCD, linear Diophantine equations, prime numbers and uniqueness of factorization. Congruences, Chinese remainder theorem, Fermat's "little" theorem, Wilson's theorem, Euler's theorem and totient function, the RSA cryptosystem. Number-theoretic functions, multiplicative functions, Möbius inversion. Primitive roots and indices. Quadratic reciprocity and the Legendre symbol. Perfect numbers, Mersenne primes, Fermat primes. Pythagorean triples, Special cases of Fermat's "last" theorem. Fibonacci numbers. Continued fractions. Distribution of primes, discussion of prime number theorem. Primality testing and factoring algorithms.


Course Policies: Homework will be due on Fridays. It can be turned in late only with advance permission from your grader. It is acceptable to use calculators and computers on homework (indeed, some of it will require a computer) but calculators are not allowed during exams. You are encouraged to work together on homework, but writeups must be done individually.

Many of the problems in this course will ask you to prove things. I expect proofs to be written in English sentences the proofs in Stein's book are a good model for the level of verbosity I am looking for.

Classificação: The grade in Math 567 will be composed of 40% homework, 20% each of three midterms. The last midterm will be take-home, and will be due on the last day of class. There will be no final exam in Math 567.

Syllabus: (This may change as we see what pace works well for the course. All section numbers refer to Stein's book.)

  • Sep 3-10: Prime numbers, prime factorizations, Euclidean algorithm and GCD (1.1-1.2)
  • Sep 13-17: The integers mod n, Euler's theorem, the phi function (2.1-2.2)
  • Sep 20-24: Modular exponentiation, primality testing, and primitive roots (2.4-2.5)
  • Sep 27-Oct 1: Public-key cryptography and RSA (3.1-3.4)
  • Oct 4 - 8: Algebraic numbers
  • Oct 6: First midterm exam
  • Oct 11-15: Quadratic reciprocity (4.1-4.4)
  • Oct 18-22: Finite and infinite continued fractions (5.1-5.3)
  • Oct 25-29: Continued fractions and diophantine approximation (5.4-5.5)
  • Nov 1-5: Diophantine equations I: Pell's equation and Lagrange's theorem
  • Nov 8-12: Elliptic curves (6.1-6.2)
  • Nov 10: Second midterm exam
  • Nov 15-19: Applications of elliptic curves (6.3-6.4)
  • Nov 22-Dec 3: Diophantine equations II: Fermat, generalized Fermat, and probabilistic methods
  • Dec 6-15: advanced topic TBD: maybe a look at the Sato-Tate conjecture?

Homework: Homework is due at the beginning of class on the specified Friday. Typing your homework is not a requirement, but if you don't already know LaTeX I highly recommend that you learn it and use it to typeset your homework. I will sometimes assign extra problems, which I will e-mail to the class list and include here.

Problem A: Use SAGE to compute the number of x in [1..N] such that x^2 + 1 is prime, for N = 100, N = 1000, and N = 10000. Let f(N) be the number of such N.

a) Can you formulate a conjecture about the relationship between f(N) and N/log N?

b) What if x^2 + 1 is replaced with x^2 + 2? Can you explain why x^2 + 2 appears less likely to be prime? (Hint: consider x mod 3.)

c) Prove that f(N) is at most (1/2)N+1. (Hint: consider x mod 2.)

d) Give as good an upper bound as you can for f(N).

Note that, despite the evident regularities you'll observe in this problem, we do not even know whether there are infinitely many primes of the form x^2 + 1! You would become very famous if you proved this.

  • Sep 17: 2.6 (the formulation of numerical evidence should be done by Sage if you've got Sage working, and by calculator if not you can use an online tool like this to test whether a number is prime.) 2.8,2.9,2.11,2.12,2.14,2.19

Problem A: Prove that if n=pq, with p,q prime, then n is not a Carmichael number.

Book problems: 2.31 (I will give a hint for this problem later in the week.) 3.4,3.5,3.6

Problem A. Prove that there are infinitely many primes p such that 2 is não a primitive root in Z/pZ. We break this up into steps. Problem A.1. Prove that, if x is an element of Z/nZ, then x^2 is not a primitive root. Problem A.2. Prove that there are infinitely many primes p such that 2 is a square in Z/pZ. Hint: suppose there are only finitely many such primes p_1, .. p_r, and define N = (p_1 .. p_r)^2 - 2. Where can you go from here. Problem A.3. Give a list of five primes p such that 2 is not a primitive root in Z/pZ (you can use the method of this proof or any other.)

Problem B. Prove that 24 is the largest integer n such that every element of (Z/nZ)^* is a root of x^2-1.

Problem A. Give a prime factorization of the Gaussian integer 7+9i.

Problem B. We showed in class that Z[i] satisfies a reduction theorem: if n and d are Gaussian integers, then there exists integers q and r such that n = qd + r and Norm(r) < Norm(d). But (by contrast with the case of Z) this d may not be unique. In some contexts it is better to be able to choose r uniquely, even if this means letting r have norm greater than Norm(d).

B.1. When d = 1+2i, show that, for each n in Z[i], there is a unique pair (q,r) in Z[i] such that n = qd+r and r is contained in the set <0,1,2,3,4>. For instance, i can be written as i(1+2i) + 2, so we say i reduces to 2 mod (1+2i). (Hint: Suppose q(1+2i)+r = q'(1+2i) + r'. What can we say about (r-r'), and why is this incompatible with both r and r' being in <0,1,2,3,4>?

B.2. Show that if n is an integer in Z, the reduction of n mod (1+2i) is equal to its reduction mod 5.

Problem C. Let's try to figure out how to define "phi(d)" for a Gaussian integer d. Suppose S is a set of Gaussian integers such that every n in Z[i] can be written uniquely as qd+r, with q in Z[i] and r in S. (So for instance when d=1+2i, we showed in problem B that we can take S to be <0. 4>. It would also be OK to take S to be <1..5>or <0,i,2i,1+i,1+2i>. In fact, it turns out that S has to be a set of size Norm(d) (I might or might not prove this in class if not, feel free just to accept it.)

Now define phi(d) to be the number of elements s of S such that s and d are coprime.

C.1. Compute phi(1+2i) and phi(3). C.2. Prove that the value of phi(d) does not depend on the choice of S. C.3. Prove that every n in Z[i] which is coprime to 3 satisfies n^phi(3) = 1 mod 3 that is, Euler's theorem holds in this case. (You can prove this by direct computation of course, if you want, you are welcome to prove that Euler's theorem holds for Z[i] in general, adapting the proof in Stein's book or the one we gave in class.)

Problem A. Express 50005 as the sum of two squares.

In the next two problems we denote by r(n) the number of ways to express n as the sum of two squares (i.e. the number of pairs (a,b) such that a^2 + b^2 = n.) For instance, r(5) = 8 (as shown on the midterm.)

Problem B. Prove that, for any N, there exists an integer n such that r(n) > N. (I.E., the function r(n) is unbounded.

Problem C. If you like Sage, write a short program in Sage to compute r(n) and compute the average of r(n) as n ranges from 1 to 1000. Whether or not you like Sage, make a guess as to how this average would behave if you replaced "1000" by a larger and larger number. (Feel free to ask the Sage-lovers what answer they got in the optional first part of the question.) Can you prove this guess is correct?

Problem D. We saw in class that the ring Z[sqrt(-5)] doesn't have unique factorization 6 can be factored as 2*3 or (1+sqrt(-5))(1-sqrt(-5)). In this problem, we will prove that Z[sqrt(-d)] fails to have unique factorization for EVERY odd d >= 5. (Actually it's true for all d >= 5 but to make the proof manageable we'll restrict to the odd case.]

D.1. Show that (1+sqrt(-d)), (1-sqrt(-d)) and 2 are primes in Z[sqrt(-d)].

D.2. Now give an element of Z[sqrt(-d)] that has two distinct factorizations into primes. (Hint: imitate the example we used for Z[sqrt(-5)].) Remark: The rings Z[sqrt(d)], where d is positive, are quite different -- here we believe that there are infinitely many with unique factorization, though this conjecture has remained unproved for many decades!

Problem E. This is a version of the proof we gave in class that the Diophantine equation y^2 = x^3 - 1 has only the solution x=1,y=0. In this problem we consider the equation y^2 = x^3 - 4.

E.1. We can rewrite the equation as (y-2i)(y+2i) = x^3. Show that, if the greatest common divisor of (y-2i) and (y+2i) is not 1, then both y-2i and y+2i are multiples of 1+i. E.2. Prove that (y-2i) and (y+2i) are relatively prime if x is odd. E.3. Using this argument, show that the only solutions to y^2 = x^3 - 4 with x odd is (11,5). OPTIONAL: Can you find the solutions where x is even?

Book problems: 4.3, 4.4, 4.6 (quite involved, counts as two problems) 4.9a

Problem A: We discussed in class the problem of studying which positive integers are the sum of two squares. In this problem we prove that every element n of (Z/pZ) is the sum of two squares. We argue as follows. Let S be the set of squares in (Z/pZ), and let T be the set of (Z/pZ) consisting of all elements of the form n - x^2, for some x in (Z/pZ).

A.1. What is the size of S and of T? Use this to show that S and T are not disjoint. A.2. Given that S and T are not disjoint, prove that n is the sum of two squares.

Problem A. Let p = 58741. Use the method of section 4.5 (discussed in class) to find an r in (Z/pZ) with r^2 = -1. Problem B. Use the result of problem A, and the method of section 5.7, to find integers a,b such that a^2 + b^2 = p. Problem C. As discussed in class, Stuffy Stirnweiss finished the 1945 season with a batting average of .3085443. Using continued fractions, guess how many at-bats he had. Tony Cuccinello had a batting average of .3084577. Given that he had more than 200 and fewer than 600 at-bats, can you estimate the number of at-bats he had?

Problem A. When p is a prime congruent to 1 mod 4, prove that ((p-1)/2)! is a square root of -1 in (Z/pZ), along the lines described on the midterm (or by some other means, if you prefer.) Problem B. When p is a prime congruent to 3 mod 4, prove that ((p-1)/2)! is either 1 or -1 in (Z/pZ). OPTIONAL: Use sage to compute whether this factorial is 1 or -1 for many primes p. Is there any pattern? Does it seem to be 1 half the time and -1 half the time? Note that I have no idea what the answer to this question is. Problem C. Using the continued fraction expansion, find a solution to the Pell equation x^2 - 13 y^2 = 1. Problem D. Show that the modified Pell equation x^2 - 7y^2 = -1 has no solutions in integers x,y. (Hint: reduce the equation modulo a suitably chosen prime.) Problem E. An ideal of Z[i] is a subset I of Z[i] which is closed under addition (if x and y are in I, then x+y is in I) and multiplication by Gaussian integers (if x is in i, then zx is also in I for every Gaussian integer z.) The set of multiples of a Gaussian integer is always an ideal (you don't need to prove this.) List all the ideals of Z[i] containing 2Z[i]. (Because such ideals satisfy conditions 1 and 2 from Monday's lecture, this list will be a subset of the list of 5 subgroups we computed in class.)

We will not go any further with the notion of ideals in Math 567, but it is worth saying that the language of ideals is absolutely essential for the understanding of contemporary number theory, in a sense "making up for" the failure of unique factorization.

Problem A. Using the method discussed in class (which is also the method of problem 4.6 in Stein, which in retrospect I think was too hard to assign with no preparation) find a nontrivial solution with y > 0 to the equation x^2 + 11y^2 = z^2. Problem B. Let f(X) be the number of solutions of A^2 + B^2 = C^3 such that A^2, B^2, and C^3 are all at most X. Use the heuristic described in class to explain why one might expect f(X) to grow more or less like X^<1/3>.

Problem C. Show that if A+Bi is the cube of a Gaussian integer, then A^2 + B^2 is a perfect cube.

Do ONE of problem D1 and D2 D1 is for people who like Sage, D2 is for people who like proving things.

D1. Use Sage to compute f(X) for X = 1000, 10000, 100000. Does the answer look consistent with the heuristic prediction you made in B? Does f(X)/X^ <1/3>appear to be approaching a limit? D2. We will use problem C to give a lower bound for f(X). Use this to show that there are at least X^ <1/3>Gaussian integers with norm at most X that are perfect cubes. From here, show that f(X) > X^<1/3>.

OPTIONAL: Show that the converse of problem C also holds -- A+Bi has norm a perfect cube if and only if A+Bi is a perfect cube. (You will need unique factorization of Gaussian integers.) Using this fact, prove that f(X) is bounded above by C X^ <1/3>for some constant C.

December 8 (note nonstandard due date)

Problem A: Hyperbolas, ellipses, and "magic slopes"

In the usual analytic geometry, both hyperbolas and ellipses are given by equations of the form


(we always assume d is nonzero.)

How can we tell whether such an equation describes an ellipse or a hyperbola? Well, in the geometric setting we all know and love (i.e. in R^2) a hyperbola has asymptotes and an ellipse does not. What is an asymptote? You could say it's "a line which doesn't intersect the curve", but ellipses have such lines too. You might want to say "a line which doesn't intersect the curve but comes closer and closer to the curve," but the problem here is that this a) is somewhat imprecise, and b) relies on a notion of "closer" that is not going to be very clear in Z/pZ, which is our ultimate goal!


So let me state it a different way: let's say the asymptotes of a hyperbola have slopes m_1 and m_2. These are "magic slopes" in the following sense: ANY line of slope m_1 (and ditto for m_2) intersects the hyperbola in at most one point. An ellipse doesn't have "magic slopes" -- you can convince yourself by drawing pictures that, for any slope m, you can find a line of slope m striking the ellipse twice.


[REMARK: For technical reasons we're going to ignore hyperbolae with a vertical asymptote, since vertical lines don't exactly have slope.]


Now you might know the criterion that, over the real numbers.


is a hyperbola if b^2 - 4ac > 0 and an ellipse if b^2 - 4ac < 0. (For instance, x^2 - y^2 = 1 is a hyperbola with magic slopes 1 and -1, and x^2 + y^2 = 1 is an ellipse.) This criterion does not make sense in Z/pZ, where there is no notion of "greater" or "less."

For which primes p is it the case that

QUESTION A.2. For which primes p is it the case that


QUESTION B: Back in the very first week of this course we studied the set of integers x such that x^2 + 1 is prime. Based on the heuristics we discussed in class, about how many x between 1 and N would you expect to satisfy "x^2 + 1 is prime?"


QUESTION C: Let z be a complex number. Then the set of all complex numbers of the form a + bz, with a and b integers, forms a lattice in the complex plane (thought of as R^2.) What is the covolume of this lattice, in terms of z?


QUESTION D: Let z be a complex number. Using Minkowski's theorem and the result of question C, show that there exist integers a,b, not both zero, such that Norm(a+bz) is at most (4/pi) Im(z). (Hint: let Omega be the set of all complex numbers of norm at most (4/pi) Im(z).)


OPTIONAL EXTRA: Can you give an exact formula for the minimal norm of any nonzero complex number of the form a+bz?


Assista o vídeo: OS TEOREMAS DE WILSON, EULER E FERMAT # (Dezembro 2021).