2019.2 FMC1, turma de Thanos

Horários: 246N12 [18h45–20h25] @ A308 (U1; U2; U3)
Sala do prof:A225
Contato:thanos@imd.ufrn.br
Aulas gravadas: 2019.2;
Study group: Telegram, atraves de link disponível em notícia do SIGAA [regras]
Monitoria/TA:fmc.imd.ufrn.br
Horário de atendimento:mande email para marcar (tente primeiro discutir tua dúvida no study group, e na monitoria)
Turmas anteriores: 2016.2; 2016.1

Prerequisitos

É prerequisito ter aprendido bem o conteudo das disciplinas Geometria Euclideana, Matemática Elementar, Análise Combinatória. Sem aprender esses assuntos primeiro, não faz sentido se matricular em FMC1. (Obs.: aprenderpassar.)

ANTES de começar seria bom estudar os:

  1. How to prove it, de Velleman (1, 2, 3)
  2. Do fmcbook os capítulos:
    • Linguagens
    • Demonstrações
  3. Mathematical Proofs, de Chartrand, Polimeni, Zhang (0, 2)
  4. Comments on style de James Munkres.
  5. A parte “Writing mathematics” do livro The tools of mathematical reasoning, de Lakins.

(Obs.: estudarler.)

Conteúdo

Conteúdo transversal (durante todas as unidades)
Lógica proposicional e de predicados (linguagem; sintaxe e semântica). Definições e demonstrações. Demonstrações diretas e indiretas, refutações. Definições por recursão – provas por indução. Os números. A linguagem de funções.
Linguagem; Típos; (U0)
Crash course!
Logica, Demonstrações; Naturais, Recursão, Indução; (U1)
Teoria dos números; Análise combinatória (U2)
Teoria dos números (U3)

Bibliografia

(Conhece o libgen?)

Principal

Auxiliar

Para cada um dos assuntos que tratamos, procure a secção «Leitura complementar» no capítulo correspondente do fmcbook para mais referências.

  • Pierce et al: Software Foundations, Volume 1: Logical Foundations [SF1]
  • Lawvere & Schanuel: Conceptual Mathematics: A first introduction to categories (I, II)
  • Velleman: How to prove it (1–3)
  • Pinter: A book of abstract algebra (2–5, 6, 12, 17)
  • Raymond Smullyan: Satan, Cantor, and Infinity
  • Raymond Smullyan: A beginner's guide to mathematical logic (Volume 1)
  • Birkhoff & Mac Lane: A survey of modern algebra (1.11; 1.1–1.5, 1.10, 1.12)

Programação

Links

Dicas

Avaliação

Pontos

A disciplina é dividida em 3 unidades (vejá Conteudo). Em cada unidade o aluno vai receber de 0 a 100 pontos. As provas escritas de cada unidade terão 100 pontos em total. (Para pegar uma idéia dessas provas, olhe nos sites das minhas turmas de FMC2 de semestres passados.)

Alem desses pontos, um aluno pode ganhar pontos extra: por participação; por homework; ou por provas-surpresas. Esses pontos valem igualmente com os pontos de prova escrita. Estou tentando ao máximo ser justo com esses pontos, mas nenhuma justificativa será dada por ganhar (ou não ganhar, ou perder!) pontos extra.

Umas regras: (1) nunca dê uma resposta que tu não pensou sozinho; (2) não tente “forçar a barra” dando respostas aleatórias nas minhas perguntas tendo como objetivo ganhar pontos extra.

Umas provas escritas podem ter pontos bônus. Esses são pontos que são condicionalmente considerados: para considerá-los um aluno precisa ter pelo menos 50pts normais (não-bônus). As questões que valem pontos-bônus são em geral em assuntos auxiliares que, mesmo que merecem ser reconhecidos, não devem ser determinantes para aprovar na disciplina.

Presenças

Veja notícia no SIGAA para informações sobre presenças, chamadas, plickers, etc.

Provas

As provas principais serão avisadas com antecedência de pelo menos 48 horas.

Unidade 1

Unidade 2

  • Prova 2.X (pts: 27; bônus: 0) (dia: 27/09/2019)
    N = { censored, uncensored, answers };
  • Prova 2.Y (pts: 9; bônus: 0) (dia: 14/10/2019)
    N = { censored, uncensored, answers };
  • Prova 2.Z (pts: 3; bônus: 0) (dia: 16/10/2019)
    N = { censored, uncensored, answers };
  • Prova 2.1 (pts: 100; bônus: 8) (dia: 18/10/2019)
    N = { censored, uncensored, answers }

Unidade 3

Reposição

  • Prova 4 (dia: 06/12/2019)

Pontos extra

Unidade 1

Pontos de participação e homework

N12
Márcio 12
Letícia 2
Tayanne 12
Andreon 22
Tiago 4
Matheus A 14
Adauto 10
Luis 7
Dawerton 10
Heitor 6
Débora 19
Wlisses 3
Fabrício 11
Francelmo 1
Lucas Gomes 4
Joel Felipe 1
Jefferson B 1
Erickson 3
Raimundo 2

Unidade 2

Pontos de participação e homework

N12
Márcio 4
Andreon 23
Luis 4
Dawerton 8
Débora 22
Fabrício 3
Lucas Gomes 4
Tayanne 9
Heitor 7
Jefferson F 2
Adauto 2
Matheus A 17
Raimundo 2
Erickson 1

Unidade 3

Pontos de participação e homework

N12
Matheus A 15
Andreon 13
Débora 15
Heitor 1
Fabrício 4
Tayanne 1
Raimundo 12
Lucas Gomes 2
Dawerton 7
Márcio 1
Micaelli 2

Homework

Obs.:

  • Estudar um assunto dum livro obviamente inclui resolver todos os exercícios e problemas.
  • «Até» é sempre inclusivo.
  • Homeworks marcados assim são opcionais; considero o resto obrigatório.
  • Depois de cada aula, um homework é sempre válido, obrigatório, e essencial: sem olhar para teu caderno, defina todas as noções e demonstre TODOS os teoremas da aula;
    while (não conseguiu) {
      estude o assunto;
      tente novamente;
    }
  • Exceto quando é explicitamente pedido, faça os homework sem consultar nenhum livro/texto/etc.

22/06/2019

  1. Estude os ítens que tenho nos prerequisitos.
  2. Brinque com Haskell ou PureScript.
  3. Estude a (pouca) coisa que tá escrita no capítulo «Estratégias de provas» do fmcbook.
  4. Estude e resolve os exercícios/problemas do capítulo 3 de Velleman.
  5. Estude o capítulo «Linguagens» do fmcbook.
  6. Estude o capítulo «A linguagem de lógica proposicional» do fmcbook.
  7. Estude os capítulos 1–2 de Velleman.
  8. Installe o Coq; dê uma lida no «Preface» do SF1 (link na Bibliografia); estude o capítulo «Basics» do SF1.

24/07/2019

  1. Capítulo 1: todo
  2. Capítulo 2: até a secção «arvores de derivação»
  3. Pense sobre os ⇒ e ⇐ e as frases «somente se» e «se» até ficar claro o qual é qual!
  4. A frase «A sse B» é equivalente à «A é necessário e suficiente para B». Qual direção corresponde ao «necessário» e qual ao «suficiente»?

28/07/2019

  1. Capítulo «Demonstrações»

29/07/2019

  1. §77. «Divisibilidade» (use no teu rascunho o tabuleiro de Dados/Alvos, mas escreva separadamente o texto mesmo (o código) das suas demonstrações.

30/07/2019

  1. Definições de «divide»: tem chances de brigar?
    D1. Sejam a,b inteiros. a divide b sse existe k inteiro tal que ak = b
    D2. Sejam a,b inteiros. a divide b sse a≠0 e existe k inteiro tal que ak=b
    D3. Sejam a,b inteiros. a divide b sse existe k≠0 inteiro tal que ak = b
    D4. Sejam a,b inteiros. a divide b sse a≠0 e existe k≠0 inteiro tal que ak=b

02/08/2019

  1. Se convença que os ataques e os usos que encontramos até agora fazem todos sentido.
  2. Θ. O √2 é irracional

03/08/2019

  1. Discutimos como «passar a negação por dentro» para proposições das formas
    • ¬(∀x)[φ(x)]
    • ¬(∃x)[φ(x)]
    mas não para proposições das formas
    • ¬(∀x∈A)[φ(x)]
    • ¬(∃x∈A)[φ(x)]
    Trate essas também em duas maneiras: (i) malandramente, reduzindo em outros casos que já tratamos; (ii) coraçãomente, argumentando diretamente com o que cada proposição dessas afirma mesmo.

04/08/2019

  1. Suponha que A denota uma proposição que tu não tens o direito de saber qual é. Mesmo assim tente demonstrar cada uma das direções, com as «regras do jogo» que temos encontrado até agora. Lembre-se que seguimos a idéia de considerar qualquer ¬P como sinônimo de (P⇒⊥)
    • A ⇒ ¬¬A
    • ¬¬A ⇒ A

07/08/2019

  1. Demonstre sem olhar em nada que √2 é irracional
  2. √6 é irracional?
  3. ³√2 é irracional?
  4. Existe irracional a tal que, aᵃ é racional? Existem irracionais a,b tal que, aᵇ é racional?

08/08/2019

  1. Sem pensar sobre nenhuma idéia nova, enuncie e demonstre uma generalização dos teoremas que demonstramos (sobre o √2 e o √3).

09/08/2019

  1. Investigue (demonstre ou refute): Cada número bonito tem raiz irracional.
  2. E o contrário? Cada número que tem raiz irracional é bonito?
  3. Tente demonstrar as duas conjecturas que encontramos na aula.
  4. Estude o capítulo «Linguagens»
  5. Estude o capítulo «A linguagem de lógica proposicional»

10/08/2019

  1. para todo n natural, demonstre que existe número real √n construindo um segmento no plano cujo comprimento é √n.
  2. podes construir um segmento cujo comprimento é ³√2?

12/08/2019

  1. Capítulo «Os números naturais»: §97–98

13/08/2019

  1. [Mateus:] Podemos trocar o «S(n+m)» da (a2) por «Sn+m»?

15/08/2019

  1. Capítulo «Os números naturais»: §99

17/08/2019

  1. Na aula passada a primeira tentativa de descrever a indução foi reduzindo nosso alvo para a Base (φ(0)) e para o (∃n)[φ(n)⇒φ(Sn)]. Mostrei um exemplo para argumentar que seria errado permitir essa regra no jogo, pois assim a gente poderia demonstrar a proposição «todo número natural é menor ou igual a 1». A gente poderia demonstrar também a proposição «todo número natural é igual a 0»?
  2. Capítulo «Os números naturais»: §§100–101

19/08/2019

  1. Capítulo «Os números naturais»: §§100–101
  2. Problemas: Π11.1

27/08/2019

  1. Na aula definimos somatório (e produtório) para seqüências finitas de números x1,...,xₙ em tal forma que a expressão x1+x2+x3+x4 acabou sendo definida como a (((x1+x2)+x3)+x4). Redefina somatório e produtório em tal forma que x1+x2+x3+x4 acabará sendo definida como a (x1+(x2+(x3+x4))).
  2. Na indução «alternativa» de Andreon/Erickson que aceitamos, parece que nem precisamos demonstrar a base. No outro lado, na nossa primeira idéia, pareceu necessaria demonstrar a base φ(8). Cadê a base agora?
  3. Mostre que não podemos supor que k>0 no passo indutivo, escolhendo uma proposição absurda que vira demonstrável com essa regra de indução que nos permite considerar que k>0 no passo indutivo. Ou seja: precisa definir uma afirmação φ(–) que é obviamente errada, e escrever uma demonstração que para todo n, φ(n), usando essa regra.

28/08/2019

  1. Na aula descobrimos que a regra de indução «a partir dum número b» não é algo que precisamos aceitar como princípio (axioma) mas podemos inferir a partir do princípio da indução «original e oficial». Faça a mesma coisa para justificar a indução com mais que uma base. Primeiramente enuncie formalmente esse princípio, e depois mostre como reduzí-lo para o princípio de indução.
  2. Existem irracionais a,b tal que, aᵇ é racional?

29/08/2019

  1. Ache uma outra maneira para justificar o princípio de indução de «a partir dum número b»

31/08/2019

  1. Podemos justificar («ganhar») o princípio da indução forte ou precisamos aceitar como princípio mesmo ?
  2. Podemos justificar («ganhar») o princípio da boa ordem ou precisamos aceitar como princípio mesmo?
  3. O 1/√2 é irracional?
  4. Estude (o problema que deixamos na aula é um dos exercícios lá)

02/09/2019

  1. Escreva um programa copiando fielmente a definicao da função A que definimos no plicker. Use para calcular os valores A(3,2) e A(7,5). Modifique teu código para contar quantas vezes a função A foi chamada, e quantas delas foram com argumentos novos.
  2. Tente estabelecer implicações entre os princípios PBO, PIF, e PIFF.
  3. Onde robei na «demonstração» dos aniversários/cavalos?
  4. Demonstre que todas as potências de qualquer ímpar são números ímpares também.

05/09/2019

  1. Dado a (ir)racionalidade do α e/ou do β podemos concluir algo sobre a (ir)racionalidade dos αβ ou α+β?
  2. Termine as direcções PIF⇒PBO e PIF⇒PIFF

06/09/2019

  1. Resolva sozinho toda a Prova 1.1.

07/09/2019

  1. G. Tendo resolvido a F, qual seria a próxima proposição para investigar sobre a função A? Enuncie claramente.
  2. Demonstre.

11/09/2019

  1. H. ∀n∀x[ Aₙ(Aₙ(x))<Aₙ₊₂(x) ]

13/09/2019

  1. Qual o problema com a gramática seguinte?:
    B ::= 0 | 1 | BB
  2. Tem algum problema com a gramática seguinte?:
    B ::= 0 | 1 | 0B | 1B
    Se não, defina a operação (–)⁺ de sucessor nessa linguagem.
  3. Dá pra definir gramática que não gera numeráis com «leading zeros» inúteis?
  4. (i) Enuncie formalmente a corretude da operação (–)⁺. (ii) Demonstre o (i).

16/09/2019

  1. Defina uma semântica para os numerais binários construidos pela B ::= 0 | 1 | 0B | 1B
  2. Demonstre a corretude da operação de sucessor que definimos nos Bin.
  3. A gramática seguinte é correta para gerar os binários sem «leading zeros»?
    N ::= 0 | P
    B ::= 0 | 1
    P ::= 1 | PB
    
    O que tu imagina que significam os N,B,P acima?
  4. Demonstre que cada b≥2 serve como base dum sistema posicional de numerais.

19/09/2019

  1. Resolva o problema Ω da Prova 4 do 2016.2.

20/09/2019

  1. Resolva o problema C da Prova 2 do 2016.1. Obs.: No C1 responde sobre Bego também. No C2 considere que Bego, antes de começar subir, ele já decidiu seus saltos e não tem percebido a existência da Catia.
  2. Demonstre o teorema binomial por indução.
  3. Resolva o problema dos caminhos de Casa para Trabalho recursivamente. O que descobriu?

23/09/2019

  1. Q: em quantas maneiras podemos formar um string por A +'s e B -'s em tal forma que não aparece o "--"?
  2. Q: em quantas maneiras podemos formar um string de tamanho k, feito pelo alfabeto {+,-}, em tal forma que não aparece o "--"?
  3. Q: quantas soluções tem uma equação x1+...+xm = k nos inteiros positivos?
  4. Q: quantas soluções tem uma equação x1+...+xm = k nos naturais?
  5. Q: O que descobriu sobre os fibonacci a partir do Aleco? Demonstre teu palpite!
  6. Teste o Monty Hall e o problema das seqüências HTH vs HTT usando tua linguagem de programação favorita. Explique os resultados.
  7. Assista essa palestra de Peter Donnelly

27/09/2019

  1. Θ:
    a|b ⇒ a|mb
    a|b & b|c ⇒ a|c
    a|b & a|c ⇒ a|(bx+cy)
    a|b & b|a ⇒ |a|=|b|
    a|b & a>0 & b>0 ⇒ a≤b
    m≠0 ⇒ (a|b ⇔ ma|mb)
    
  2. Θ: Se um conjunto S de inteiros é fechado pela adição e pela subtração então S={Ø} ou existe positivo inteiro d tal que S={md|m∈ℤ}.
  3. Q: no Θ acima precisamos mesmo ambas as hipoteses sobre o S?

28/09/2019

  1. Resolva a Prova 2.X

30/09/2019

  1. Mostre que modemos inferir o princípio da indução que encontramos nos inteiros a partir dos princípio da indução original.
  2. Sejam a,b inteiros. Demonstre que existe um maior divisor comum deles d, e que ele pode ser escrito como «combinação linear» deles, ou seja, que existem inteiros x,y tais que d = ax + by.
  3. Mostre que existe exatamente um maior divisor comum não-negativo. É esse que denotamos por gcd(a,b) (ou por (a,b) se não existe ambigüidade).
  4. Os x,y são determinados pelos a e b? Ou seja, a forma de escrever o d como combinação linear dos a e b é única?
  5. Resolva o plicker: d|ab ⇐?⇒ (d|a ou d|b)

05/10/2019

  1. Demonstre ou refute: para quaisquer inteiros a,b, os seguintes são todos iguais: (a,b), (-a,b), (a,-b), (-a,-b), (b,a)
  2. (a,b) =?= (a,a+b)
  3. (a,b) =?= (a,ax+b)
  4. (a,b) =?= (a,ax+by)
  5. Para quaisquer inteiros a,b, e qualquer primo p:
    p|ab ⇒ (p|a ou p|b)
  6. a|m & b|m ⇐?⇒ ab|m
  7. d|a+b ⇒?⇒ d|a ou d|b
  8. Podes afirmar algo sobre o (a,p)?

07/10/2019

  1. Todo inteiro exceto o 0 pode ser escrito como produtorio de primos. dica: use uma certa versao de indução que encontramos na unidade 1

08/10/2019

  1. Divisão de Euclides: demonstre a unicidade de quociente e resto
  2. Lemma de Euclides: p|ab ⇒ p|a ou p|b: demonstre sozinho
  3. ?? & d|ab ⇒ d|b: Pelo lemma de Euclides sabemos que «d primo & d∤a» serve para os «??». Ache uma afirmação mais geral que essa que também serve para os «??» e demonstre.
  4. ?? & a|m & b|m ⇒ ab|m: o que botar no «??»? Demonstre tua afirmação.
  5. Teorema fundamental de aritmetica: demonstre a unicidade da fatorização («módulo» a ordem dos fatores)
  6. No fim da última aula descobrimos que podemos representar cada inteiro positivo por uma lista finita de naturais, correspondendo nos exponentes (veja teorema fundamental de aritmética). O que muda se em vez de naturais usar inteiros?

09/10/2019

  1. Demonstre os teoremas principais até agora: Divisão de Euclides ; existência e forma de mdc ; teorema fundamental de aritmética ; lemma de euclides (p|ab ⇒ p|a ou p|b)
  2. Termine nossa primeira demonstração do «The Book»: (Euclides): existe uma infinidade de primos
  3. Calcule os mdc's: (14,35) ; (11,15) ; (2873,6643) ; (4148,7684) ; (1001,7655)
  4. Escreva cada um dos (a,b) do exercício anterior como combinação linear dos a e b
  5. Demonstre ou refute: (ab,ac) =?= a(b,c)
  6. ?? & d|ab ⇒ d|b: Pelo lemma de Euclides sabemos que «d primo & d∤a» serve para os «??».
  7. Demonstre ou refute: «se q é um inteiro tal que para quaisquer inteiros a e b, q|ab implica em q|a ou q|b, então q é 0, 1, -1, ou primo.»
  8. Demonstre ou refute: (a,m) = (b,m) = 1 ⇒ (ab,m) = 1
  9. Demonstre: a|c & b|c ⇒ ab | c(a,b)

10/10/2019

  1. Quão a eficiência do algoritmo de Euclides?

11/10/2019

  1. Dica: calcule o (89,55)
  2. A dica acima foi dica para qual problema?
  3. Θ: para todo n≥2, existe primo entre n e n!
  4. Θ: para todo n, existem n consecutivos compostos
  5. Q: Quando eu posso parar, usando o crivo de Eratosthenes?
  6. Demonstre o que precisa demonstrar para justificar a definição do menor múltiplo comum e da sua notação lcm(–,–) (também: [–,–]). Compare com a demonstração sobre o m.d.c.
  7. [a,b] = ab/(a,b)
  8. Vₚ(a+b) ≥ min( Vₚ(a) , Vₚ(b) )
  9. Vₚ((a,b)) = min( Vₚ(a), Vₚ(b) )
  10. Vₚ(ab) = Vₚ(a) + Vₚ(b)
  11. Vₚ([a,b]) = max( Vₚ(a), Vₚ(b) )
  12. ‖ab‖ₚ = ‖a‖ₚ‖b‖ₚ
  13. ‖a+b‖ₚ ≤ max( ‖a‖ₚ , ‖b‖ₚ )
  14. Um inteiro x é chamado quadrado sse existe inteiro b tal que x = b². Preenche os «??» e demonstre que: mn quadrado & ?? ⇒ m,n quadrados

14/10/2019

  1. Resolva bem a Prova 2.Y
  2. Resolva bem a parte da unicidade do teorema da Prova 2.Y

16/10/2019

  1. Demonstre que Matheus não foi bipolar na aula: as duas definições de a,b congruentes módulo m são equivalentes.

19/10/2019

  1. Resolva toda a Prova 2.1.

19/10/2019

  1. Pelamor de Ευκλείδης, resolva o J da Prova 2.1 e termine o E1.
  2. Construa as tabelas de adição e multiplicação para os ℤ₂,ℤ₃,ℤ₄,ℤ₅,ℤ₆,ℤ₇
  3. Olhando para as 12 tabelas que tu construiu no homework anterior, ache propriedades interessantes dessas 12 operações
  4. Chamamos um número u de unit sse u|1. Quais são (se tem!) os units dos: ℤ,ℤ₂,ℤ₃,ℤ₄,ℤ₅,ℤ₆,ℤ₇
  5. Chamamos um número d de zerodivisor sse existe número k≠0 tal que dk=0. Quais são (se tem!) os zerodivisores dos: ℤ,ℤ₂,ℤ₃,ℤ₄,ℤ₅,ℤ₆,ℤ₇
  6. ca≡cb (mod m) ⇐?⇒ a≡b (mod m)
  7. a+c≡b+c (mod m) ⇐?⇒ a≡b (mod m)
  8. a≡b (mod m) ⇐?⇒ -a≡-b (mod m)
  9. Justifique a perigosa definição da adição e multiplicação módulo m que discutimos na aula. (Aquela que usou a regra de «escolhe dois representantes, opera nos inteiros, retorna a classe do resultado».) Enuncie o que precisa ser demonstrado, e demonstre.
  10. Para qualquer m, as operações de adição e multiplicação módulo m são: associativas, comutativas, possuem identidade (elemento neutro), e +-inversos (negação de número). Possuem ·-inversos (inverso multiplicativo de número).

23/10/2019

  1. Sejam a,b,m inteiros com m≥1 e (a,m)=1. A congruência ax≡b (mod m) tem resolução para o x. É única?

30/10/2019

  1. Se p,q são primos distintos e pq|n², então pq|n.
  2. Os 2ⁿ-1,2ⁿ+1 não são primos gemeos, exceto para n=2.
  3. Demonstre que para exatamente um k inteiro, os k, k+2, k+4 são primos.
  4. Cada número da forma 3k+2 possui fator primo da mesma forma. Dica: todos os fatores primos são ou do time 0 ou do time 1 ou do time 2. Mostre que ninguem tá no time 0, e que é impossível que todos são do time 1.
  5. Sabemos que tem uma infinidade de primos. Quantos deles são congruentes ao 0 módulo 4? Quantos ao 2? Demonstre que tem uma infinidade deles congruentes ao 3. Dica: inspira-se pela demonstração da infinidade de primos de Euclides, e pela tua demonstração do exercício anterior.
  6. Sejam n≥1 e S um conjunto de de n+1 inteiros positivos, todos menores ou iguais ao 2n. Existem distintos a,b∈S tais que a|b. Dica: cada inteiro positivo pode ser escrito na forma 2ᵏr, com r ímpar.
  7. Investigue o que deixamos da resolução geral da congruência ax≡b (mod m).
  8. Termine o fim do sistema de duas congruências que eu buguei no fim da aula; observe porque tá praticamente resolvido.
  9. Tente generalizar a idéia para um sistema de n congruências.
  10. Demonstre o sonho de calouro: (x+y)ᵖ≡xᵖ+yᵖ (mod p).
  11. Demonstre: aᵖ≡a (mod p). Dica: indução, e exercício anterior.

05/11/2019

  1. Ache todos os inteiros x com |x|<64 que satisfazem o sistema de congruências:
    x≡1 (mod 3)
    3x≡1 (mod 4)
    4x≡2 (mod 5)
  2. Resolva:
    x≡3 (mod 4)
    5x≡1 (mod 7)
    x≡2 (mod 9)
  3. Resolva:
    x≡3 (mod 3)
    3x≡3 (mod 4)
    4x≡2 (mod 5)
    5x≡1 (mod 7)
  4. Resolva:
    5x≡2 (mod 6)
    x≡13 (mod 15)
    x≡2 (mod 7)
  5. Resolva:
    x≡2 (mod 6)
    x≡13 (mod 15)
    x≡2 (mod 7)

07/11/2019

  1. φ é multiplicativa (a,b)=1 ⇒ φ(ab) = φ(a)φ(b)
  2. Eficiência de Euclides: o que acontece depois de dois passos?
  3. Caso geral da ax≡b (mod m)
  4. (p-1)!≡-1 (mod p) ⇐?⇒ p primo
  5. Converso de Fermat: verdade ou falso?
    Se para todo a, aᵖ≡a (mod p), então p é primo.
  6. Demonstre o que faltou para terminar a demonstração da Debora: (r,n) = (n-r,n)
  7. (a,bc) = 1 ⇐?⇒ (a,b)=1&(a,c)=1
  8. (qm+r,m) = (r,m)

08/11/2019

  1. φ é multiplicativa (a,b)=1 ⇒ φ(ab) = φ(a)φ(b)
    Dicas: escreva os mn números de 1 até mn numa tabela m×n. Argumente que so tem φ(m) colúnas com números coprimos ao m. Argumente que em cada coluna dessas tem φ(n) números coprimos ao n. Use os dois últimos hw do dia 07/11/2019.
  2. Demonstre ou refute: (p-1)!≡-1 (mod p) ⇒ p primo
  3. Converso de Fermat: refute: Se para todo a, aᵖ≡a (mod p), então p é primo.
    Dica: 561
  4. Verifique que 341 engana Fermat com base a:=2
    Dica: Lema que demonstramos na aula; Fatorize o 341; e 1023 = 31·33

11/11/2019

  1. Pelamor de Leonhard, faça todo o homework que não tem feito ainda.
  2. Lemma (ResSys): Sejam a,m coprimos, e R={r₁,r₂,…,rₙ} um sistema completo ou reduzido de resíduos módulo m. Então aR={ar₁,ar₂,…,arₙ} também é completo ou reduzido respectivamente.

Definição. Se x≡y (mod m) chamamos o y um resíduo de x módulo m. Seja conjunto R={r₁,r₂,…,rₙ} de inteiros. Chamamos o R de sistema completo de resíduos módulo m sse para todo inteiro x existe único r∈R tal que r é um resíduo de x módulo m. Chamamos o R de sistema reduzido de resíduos módulo m sse: (1) todos os membros de R são coprimos com m; (2) rᵢ≡ₘrⱼ ⇒ i=j; e (3) para todo inteiro x coprimo com m, existe r∈R tal que r é um resíduo de x módulo m.

27/11/2019

  1. Como podemos recuperar os p,q se conseguirmos o φ(N)?

29/11/2019

  1. Demonstre o teorema da Prova 3.X sem a hipótese (x,N)=1.

Histórico de aulas

24/07/2019: Introdução [video]

  • Apresentação dos assuntos principais
  • Os típos principais: proposições (tbm: afirmações); objetos (tbm: individuais)
  • Erros comuns
  • Type error
  • Erro de semântica
  • Diferença entre as duas frases:
    • «Se __A__, (então) __B__.»
    • «Como __A__, (logo) __B__.»
  • O significado da palavra «equivalente» em matemática
  • Noções primitivas – Definições
  • Axiomas – Teoremas
  • Sinônimos de «teorema» e seus usos: lema, corolário
  • Hipótese; tese
  • Programando programas vs. provando teoremas
  • Lemmata como funções e bibliotecas de programação
  • Árvores de derivação

26/07/2019: Introdução; Demonstrações [video]

  • Decepção e recap
  • implicação em matemática
  • «se» vs «somente se»
  • «necessário» vs «suficiente»
  • Erro: afirmação do conseqüente
  • Conjunção: como atacar e como usar
  • Um exemplo de demonstração e seu tabuleiro
  • Definições
  • contexto de definição
  • variáveis livres e ligadas
  • duas maneiras que uma definição pode ser errada
  • igualdade vs equivalência, com e sem «def»
  • declarar vs definir
  • Um exemplo de demonstração (cont.)
  • notação de conjuntos
  • Existência: como atacar e como usar

29/07/2019: Demonstrações [video]

  • Recap: açúcares sintácticos que já encontramos
  • (∃x∈A)[φ(x)] e (∀x∈A)[φ(x)] como açúcar sintáctico
  • Θ: todos os quadrados de ímpares são ímpares
  • «para algum» e CUIDADO: não use a «vírgula mágica», nem um «para» seco
  • propriedades de igualdade
  • «Calculamos»
  • D: divide
  • Θ: O 1 divide todos os inteiros
  • Θ: Cada inteiro divide ele mesmo

31/07/2019: Demonstrações [video]

  • Dois enunciados dum teorema: mesma coisa ou não?
  • Θ: (∀a∈ℤ)[a|0]
  • Demonstração errada: podemos inferir algo?
  • Θ: (∀a,b,x∈ℤ)[a|b ⇒ a|bx]
  • Como justificar uma coisa «obvia» de igualdade
  • Quantificadores consecutivos
  • Θ: (∀a,b∈ℤ)[a|b ⇒ (a|-b e -a|b)]
  • atacando conjunções
  • Utilizando teoremas demonstrados como lemmata
  • usando afirmações universais
  • Θ: (∀a,b,c∈ℤ)[(a|b e a|c) ⇒ a|b+c)]
  • mais uma justificação de algo «óbvio»
  • Θ: (∀a,b,c,x,y∈ℤ)[a|b e a|c ⇒ a|bx+cy]
  • usando implicações: modus ponens

02/08/2019: Demonstrações [video]

  • Θ: (∀a,b,c∈ℤ)[a|b e b|c ⇒ a|c]
  • Stocktaking/bookkeeping
  • Disjunção: como atacar
  • Separação em casos
  • LEM (Law of Excluded Middle)
  • Resumindo numa maneira mais humana
  • Disjunção: como usar
  • Uma resposta malandra
  • Uma resposta direta
  • Tratando negação
  • A ⇐?⇒ ¬¬A
  • Como usar
  • Θ: O √2 é irracional
  • D: (ir)racional
  • D: √2
  • «aquele ... que ...»

05/08/2019: irracionalidade [video]

  • Θ: O √2 é irracional
  • «aquele ... tal ...»
  • existência e unicidade
  • um enunciado errado de lemma
  • um enunciado dum lemma que não nos ajuda
  • um enunciado dum lemma que nos ajuda sim
  • implicação: outra maneira para atacar
  • a contrapositiva de implicação
  • uma demonstração com erros
  • não confunda «tal que» com «e»
  • a importância enorme do que demonstramos
  • Wason's test

07/08/2019: irracionalidade [video]

  • Recap: Θ: O √2 é irracional
  • perguntando nossas próprias perguntas
  • Θ? O √3 é irracional
  • tentando copiar «mutatis mutandis» uma demonstração
  • dois teoremas fortes que não demonstramos ainda
  • dificuldade: demonstrar ou refutar?
  • demonstrado o lema que queremos
  • o que ganhamos brincando com o 4
  • separando números em «times» a partir dum número-guia
  • separando em casos
  • cadê o problema com o lemma sobre o 4?
  • esse √3 é um número mesmo?
  • para quais números x o √x é racional?
  • umas questões sobre primos e raizes racionais
  • o √6 é irracional?

09/08/2019: demonstrações; linguagens [video]

  • Demonstrações
    • perguntando nossas próprias perguntas
    • generalizando um teorema
    • generalizando uma definição
    • perguntando o contrário
    • as conjecturas da aula passada são verdadeiras?
    • sobre a redução ao absurdo
  • Linguagens
    • sintaxe vs semântica
    • definindo linguagens
    • gramáticas e notação BNF
    • erro de ética: escolhe nomes bons e honestos
    • dígito vs numeral vs número
    • convenções e açúcar sintáctico
    • linguagens com variáveis
    • «arbitrariamente grande»
    • metalinguagem e metavariáveis

12/08/2019: Demonstrações; Naturais, recursão, indução [video]

  • Demonstrações
    • Dupla negação
    • Como demonstrar que √n é definido para cada n natural
    • o ³√2 é irracional?
  • Naturais, recursão, indução
    • Nat(urais): uma definição humana
    • um acordo sobre afirmações com (meta)variáveis não declaradas
    • voltando: variável vs metavariável
    • Nat(urais): uma definição com gramática
    • Nat(urais): uma definição com regras de inferência
    • Um açúcar sintáctico
    • os valores canônicos de Nats
    • função vs construtor
    • Numerais diferentes
    • Spoiler/trailer: seqüências, funções, FMC2
    • Igualdade
    • cuidado: os «para todo» e «existe»
    • Recursão
    • 2+3=5
    • Resumo: o que aconteceu

14/08/2019: Naturais, recursão, indução [video]

  • Recap: Nat(urais)
  • Recursão vs tijolo
  • Calculando a soma com recursão
  • onde focar para reduzir?
  • Multiplicação
  • 2 · 3 = 6
  • qual resultado incompleto é melhor?
  • precedência e associatividade de operadores
  • Θ. Associatividade da +
  • tem como continuar a demonstração?
  • escolhendo variáveis com «linhas»: x', x'', etc.
  • o problema que temos demonstrando esse teorema

16/08/2019: Naturais, recursão, indução [video]

  • Recap: tentativa de demonstrar
  • a recursão foi no segundo argumento, então...
  • «para ALGUM»
  • Recursão – Indução
  • Indução
  • quando podemos usar indução
  • indução informalmente
  • indução expressa com conjunto
  • «conjunto fechado por...»
  • Esqueçam a receitinha de 3 passos!
  • Indução como regra de inferência
  • «Base» e «Passo indutivo»
  • a regra de indução na verdade é um esquema
  • indução para demonstrar nosso teorema atual
  • «hipótese indutiva»
  • Como podemos continuar agora?
  • Briga: poluição do estado com novos nomes novos «para abreviar»
  • Podemos continuar assim também!
  • continuando a demonstração
  • presente da recursão vs presente da indução
  • continuando a demonstração
  • Algo que NÃO é supor o próprio alvo!
  • Donde chegou essa paréntese?
  • continuando o cálculo
  • donde chegou essa paréntese?
  • propriedades de igualdade
  • o que aconteceu
  • E se eu nem precisei usar a hipótese indutiva?
  • Faz diferença se escolher usar indução mais cedo?

19/08/2019: Naturais, recursão, indução [video]

  • exponenciação
  • recap: associatividade da +
  • tentar começar «por indução»
  • melhor, pior, ou mesma coisa?
  • «por indução no z»
  • podemos trocar quantificadores consecutivos da mesma forma
  • discussão: comparação das duas demonstrações
  • comparando as H.I.'s
  • com a regra errada podemos demonstrar que todo natural é igual a 0?
  • drinker's paradox
  • o que ganhamos
  • Θ: + é comutativa
  • 0 + 0 = 0 + 0 sem nem calcular
  • lemmas em demonstrações
  • comparação com programação
  • subinduções
  • lendo as H.I. «com palavras da rua»
  • escopos e escolhas de variáveis

21/08/2019: Naturais, recursão, indução [video]

  • Θ: + é comutativa: o esqueleto
  • escopos e as várias hipoteses indutivas
  • entender no coração, com palavras da rua
  • passo indutivo da segunda sub-indução
  • matemática é case-sensitive!
  • usando o ` ≟ '
  • observações
  • adição, multiplicação, exponenciação, e depois?
  • Θ: · é associativa
  • lemmata em demonstrações
  • escolhendo nomes lindos para nossas variáveis
  • um erro no esboço da prova!
  • Entendi tudo!

26/08/2019: Naturais, recursão, indução [video]

  • associativa vs associativa-a-esquerda/direita
  • generalizando operação binária para n-ária, com n≥0
  • seqüências finitas e infinitas, convenções com os «...»
  • off-by-one error
  • definição formal (recursiva) de somatório e produtório
  • como definir a «próxima» operação depois da exponenciação
  • indução «a partir dum númer positivo»
  • «vacuamente verdade»
  • Posso assumir k>8?
  • Cadê a base?

28/08/2019: Naturais, recursão, indução [video]

  • justificando a regra de «indução a partir de» sem aceitar como princípio
  • o que significa ≤ ?
  • roubando usando língua, etimologia, notação, etc.
  • definindo relações recursivamente
  • programação declarativa: programação funcional e programação lógica
  • um lemma importante sobre a ≤
  • por que não podemos supor k>0 no passo indutivo?
  • descobrindo mais «princípios» relacionados
  • uns cuidados para tomar levantando de low-level para high-level
  • umas maneiras de definir a função fibonacci
  • definição dos números Lucas
  • como calcular valores dessas funções
  • exercício: L = ℓ
  • duas maneiras de organizar o passo indutivo
  • cuidado não escrever objetos não definidos!
  • quando uma base não é suficiente
  • survey: tem irracionais a,b tais que aᵇ é racional?

30/08/2019: Naturais, recursão, indução [video]

  • tem irracionais a,b tais que aᵇ é racional?
  • NUNCA dê nenhum espaço desnecessário para teu inimigo!
  • 1/√2 é irracional? (fácil)
  • 2^(1/√2) é irracional? (difícil)
  • uma demonstração clássica
  • de SQL injection para lógica matemática
  • «abusando» o princípio da indução
  • ganhando a «indução a partir de»
  • maneiras diferentes de organizar uma demonstração por indução
  • princípio da indução original
  • princípio da indução com mais bases
  • ganhando a «indução com mais bases»
  • o que aconteceu?
  • dica: como começar sem saber se/qual indução vai precisar
  • indução forte
  • tem base?
  • Q: podemos «ganhar» a partir da original?
  • dica de novo: como começar sem saber se/qual indução vai precisar
  • o princípio da boa ordem
  • Todos os naturais a partir de 8 podem ser escritos como somatório de 3s e 5s
  • uma dica seguindo um possível caminho

02/09/2019: Naturais, recursão, indução [video]

  • indução forte
  • princípio da boa ordem (PBO)
  • como usar o PBO na prática
  • exemplo: não existem inteiros entre 0 e 1
  • entendendo o princípio da indução
  • indução e recursão: dois lados da mesma moeda
  • princípio da recursão
  • sobre implicação
  • Wason's test com psicologia diferente
  • implicação material vs relevante
  • uma demonstração errada: cavalos e aniversários
  • triminôs: de prova por indução para um algoritmo
  • uma recursão aninhada: quantas chamadas?

04/09/2019: Naturais, recursão, indução; Teoria dos números [video]

  • o 1/√2 é racional?
  • soma e produto de (ir)racionais é (ir)racional?
  • Todas as potências de um ímpar são ímpares
  • escolhendo nomes de variáveis
  • podemos mexer com os quantificadores duma implicação?
  • onde roubei na «demonstração» dos aniversários
  • corolário simples do teorema dos triminôs
  • implicações entre PIF,PIFF,PBO
  • PBO ⇒ PIF
  • PIF ⇒ PIFF (dica)
  • PIF ⇒ PBO (dica)
  • Fortalecendo o enunciando: teorema de pontinhos
  • de novo: quantas chamadas precisamos?

06/09/2019: Prova 1

09/09/2019: Sermão ; Resolução da Prova 1.1 [video]

  • Resolução da Prova 1.1 (A–E)
  • aridade
  • contexto de definição
  • não escreva: «sendo», «para x», «com»
  • português matemático
  • keywords low-level em demonstrações
  • «logo» vs «ou seja»
  • «existe» vs «seja»
  • «procuro ...» vs sem nome
  • sobre cálculos e «calculamos»
  • proposição vs declaração
  • «suponha» vs «seja»
  • Reclamação: procurem usar seus recursos (compiladores humanos nesse caso)
  • onde e quando usar indução
  • uma resolução mais econômica
  • qual é a base?
  • somatório vazio
  • cuidado com indução: onde a quando?
  • essa vez o quando importa!
  • descreva tanto formalmente quanto com palavras de rua!
  • Survey: ficou surpreso com tua nota?

11/09/2019: Resolução da Prova 1.1 [video]

  • F. ∀n[ Aₙ é estritamente crescente ]
  • Como começaria a demonstração?
  • Demonstração do F
  • G1. Enuncie a G2 e demonstre.
  • G2. ∀n∀x[ Aₙ(x) é menor que Aₙ₊₁(x) ]
  • E sobre o A₄?

13/09/2019: Naturais, recursão, indução [video]

  • Θ. ∀n∀x[ Aₙ(Aₙ(x))<Aₙ₊₂(x) ]
  • Outras linguagens de númerais: Bin
  • Como definir operações no Bin
  • De sintaxe para semântica: um toque de semântica denotacional

16/09/2019: Naturais, recursão, indução ; Análise combinatória [video]

  • sistemas posicionais de numerais
  • bin, oct, dec, hex, ...
  • Θ. (∀b≥1)[b serve como base dum sistema posicional de numerais]
  • ou seja: (∀b≥1)(∀x)(∃n≥0)(∃c₀,…,cₙ)[x = Σcᵢbⁱ]
  • qual a restrição nos coeficientes?
  • A linguagem Bin dos numerais binários
  • qual o problema com aquela que usa BB ?
  • Enunciando a corretude do sucessor que definimos nos Bins
  • diagrama comutativo: nosso primeiro
  • Como demonstrar a corretude
  • donde que chegou o princípio da indução mesmo?
  • o princípio da indução (e da recursão) no Bin
  • Roubamos usando operações dos naturais?
  • Basta só demonstrar por indução
  • quais são as hipoteses indutivas?
  • o que observamos sobre a gramática que bota os bits no início?
  • como podemos definir (nativamente) a semântica e como o sucessor?
  • Umas gramáticas que não geram numerais com «leading zeros»
  • Como vamos trabalhar estudando teoria dos números
  • Um toque de análise combinatória
  • o que se trata
  • princípio da adição e da multiplicação
  • erros comuns
  • temos confiança?

18/09/2019: Análise combinatória [video]

  • princípios da adição e multiplicação
  • derivando o princípio da multiplicação a partir o princípio da adição
  • quando (não) podemos adicionar
  • quando (não) podemos multiplicar
  • quantas palavras ordenadas
  • permutações e combinações
  • definição com palavras de contagem
  • chegando em fórmulas (definições equivalentes)
  • Ptot(n)
  • P(n,k)
  • off-by-one!
  • C(n,k): hipercotando via P(n,k); e com recursão
  • demonstrações com argumentos combinatórios
  • Q: como 10 amigos podem viajar com um carro?
  • contando com idéias diferentes
  • Q: como ir de casa para o trabalho?
  • modelando/traduzindo fielmente a pergunta para outra
  • ∀n∀k[ C(n,k) = C(n,n-k) ]
  • Q: e se quiser evitar uma rua?
  • as vezes é mais fácil contar o complemento
  • Q: como sentar num bar?
  • Q: como sentar numa mesa redonda?
  • Q: como sentar num bar, mas agora com brigados
  • Q: permutar as letras da palavra PESSIMISSIMO
  • a gente sabia quanto % dessa aula?

20/09/2019: Naturais, indução, recursão ; Análise combinatória [video]

  • como definir semântica na gramática dos binários que bota os bits na frente
  • No(ta)ções de conjuntos
  • interface de conjunto
  • operações: união ; intersecção ; diferença
  • subconjunto (próprio)
  • set-builder (comprehensão)
  • igualdade de conjuntos
  • cuidado com os símbolos '⊂' e '⊈'
  • Q: quantos subconjuntos?
  • o conjunto vazio
  • usando o princípio da adição
  • usando uma tradução (modelo)
  • a recursão do C(n,k)
  • como calcular
  • (x+y)ⁿ
  • entendendo o teorema binomial
  • contando recursivamente: Aleco e Bego
  • a palavra «respectivamente»
  • quais são as bases da recursão?

23/09/2019: Análise combinatória [video]

  • contando recursivamente: Aleco e Bego
  • oportunidade de homework!
  • probabilidade elementária
  • de-caso-pro-trampo recursivamente
  • floor e ceiling
  • recursando mais rapido
  • nomear e conquistar
  • o mago Xyzzy e seus lemmings
  • Θ. o teorema binomial
  • quatro perguntas de contagem
  • Monty Hall
  • plicker: avg(HTH) vs avg(HTT)

25/09/2019: Análise combinatória ; teoria dos números [video]

  • análise combinatória
    • de Aleco para Fibonacci
    • palavras do {+,-} sem "--"
    • olhando para o triângulo de Pascal
    • resolução de equações com restrições: (i) positivos; (ii) não-negativos
    • Umas aplicações do teorema binomial
    • Torres do Hanoi
    • O problema de Josephus
  • teoria dos números
    • quebrando os números até chegar em tijolos
    • com cimento a adição
    • com cimento a multiplicação
    • Θ (Euclides). existe uma infinidade de primos
    • discussão curta sobre os homeworks da probabilidade
    • lemma da divisão de Euclides
    • D: conjunto fechado por operação
    • Θ: Se um conjunto S de inteiros é fechado pelas + e -, então ou S = {0} ou S = {md | m∈ℤ}
    • Θ: não existe inteiro entre 0 e 1
    • Presente?

27/09/2019: Teoria dos números ; Prova 2.X [video]

  • discussão: torres de Hanoi
  • presente da recursão no coração
  • Θ: propriedades de divisibilidade
  • D: Conjunto fechado por operação
  • o vazio é fechado por qualquer operação
  • Θ: o lemma da divisão de Euclides
  • importância e como usar
  • dica para demonstrar
  • Θ: S≠Ø e S fechado pelas + e - ⇒ S={0} ou
  • Θ: Se um conjunto S de inteiros é fechado pelas + e -, então ou S = {0} ou S = {md | m∈ℤ}
  • o paradoxo da surpresa
  • Prova (surpresa) 2.X

30/09/2019: Teoria dos números [video]

  • Θ: conjuntos fechados pelas +,-
  • a idéia da demonstração
  • A1: justificar o uso da PBO
  • como atacar igualdade de conjuntos
  • A2: o S tem todos os múltiplos de d
  • A3: o S não tem lixo: (nada mais exceto múltiplos de d)
  • Um princípio de indução para inteiors
  • Lemma de divisão de Euclides
  • existência
  • como atacar a unicidade
  • relações de ordem
  • mdc (maior divisor comum)
  • Definição de mdc (com erros)
  • 0|x? x|0?
  • a|b vs a/b
  • existência de tal objeto
  • unicidade de tal objeto
  • artigo definido vs artigo indefinido
  • Θ. existe unico m.d.c. não negativo
  • dica para demonstrar
  • d|ab ⇐?⇒ (d|a ou d|b)

02/10/2019

04/10/2019: Teoria dos números [video]

  • d|ab ⇒ (d|a ou d|b)
  • refutação de: «para todo ...»
  • refutação de: implicação
  • refutação de: disjunção
  • d|ab ⇐ (d|a ou d|b)
  • «similar»?
  • Palpite: p|ab ⇒ (p|a ou p|b)
  • os números primos
  • D: m.d.c.
  • cuidados com definições
  • artigo «definido» vs «indefinido»
  • obrigações para introduzir notação (de operação)
  • Existência e unicidade
  • Existe um m.d.c.
  • Lemma (da Prova 2.X)
  • Existe um m.d.c [cont.]
  • o conjunto S das combinações lineares dos a,b não é vazio
  • S é fechado pela -
  • o d que ganhamos (graças ao Lemma 2X) é o que procuramos
  • unicidade «módulo módulos»
  • o que ganhamos?
  • os coeficientes não são determinados pelos a,b
  • uma maneira de mostrar que (a,b) = (c,d)
  • a|b ⇒ (a,b) = a
  • (a,0) = a
  • os (a,b), (-a,b), (b,a) são todos iguais? (a,b) =?= (a,a+b)

07/10/2019: Teoria dos números [video]

  • Recap
  • lemma da divisão de Euclides
  • «sem perda de generalidade»
  • notações: comdiv(–,–) e divs(–)
  • novamente: uma maneira de mostrar que (a,b) = (c,d)
  • (a,b) = (-a,b) = (b,a) [= (a,-b) = (-a,-b)]
  • (a,b) = (a,a+b)
  • (a,b) = (a,ax+b)
  • em geral (a,b) ≠ (a,a+by)
  • D: primo e composto
  • «exatamente»
  • Lemma de Euclides: p|ab ⇒ p|a ou p|b
  • Teorema fundamental de aritmética
  • existência
  • uma demonstração errada da unicidade
  • inteiros positivos como lista finita de naturais
  • o que acontece se trocar os naturais por inteiros?
  • a|m e b|m ⇐?⇒ ab|m

09/10/2019: Teoria dos números [video]

  • Θ: lemma da divisão de Euclides
  • existência
  • unicidade
  • algoritmo
  • Corolários do lemma de Euclides
  • representação de inteiros como listas finitas de naturais
  • o algoritmo de Euclides
  • corretude
  • eficiência do algoritmo
  • um exemplo: (252,180)
  • metodo da criança brasileira
  • algoritmo de Euclides: ainda mais legal
  • algoritmo de Euclides: terminação
  • Erdős: «The Book»
  • Θ: teorema de Euclides: infinidade de primos
  • (ab,ac) =?= a(b,c)

11/10/2019: Teoria dos números [video]

  • (ab,ac) = |a|(b,c)
  • sobre a eficiência do algoritmo de Euclides
  • sobre o teorema fundamental da aritmética
  • unicidade
  • Θ (Euclides): tem uma infinidade de primos
  • a distribuição dos primos
  • a conjectura de primos gêmeos
  • entre n e n! tem primo
  • prime gaps
  • para todo n, existem n consecutivos compostos
  • crivo de Eratosthenes
  • quando eu paro?
  • menor múltiplo comum (lcm(–,–) ou [–,–])
  • desenhando os inteiros não-negativos a partir da ordem |
  • ab = [a,b](a,b)
  • o que precisamos demonstrar para justificar a definição?
  • lcm e gcd a partir de fatorização em primos
  • o teorema dos números primos
  • uma viagem sobre tamanhos e distâncias baseadas em primos
  • p-valuações dos (a,b) e [a,b] em termos das p-valuações dos a e b[01:35:53]

14/10/2019: Teoria dos números; Prova 2.Y [video]

  • Dicas sobre os homeworks
  • Existem ℓ consecutivos compostos
  • Formalizando o enunciado
  • idéias para não seguir e uma dica
  • Existe primo entre n e n!
  • Θ: b-expansão de números
  • enunciado e sua tradução
  • Prova 2.Y: demonstre!
  • dica
  • rascunho de demonstração
  • Tô aqui!

16/10/2019: Teoria dos números ; Prova 2.Z [video]

  • Existem ℓ consecutivos compostos
  • A conjectura dos primos gêmeos
  • A conjectura de Goldbach
  • fraca ⇐ forte
  • gcd(89,55)
  • (m,n)=1 e mn quadrado ⇒ m,n quadrados
  • entre n e n! tem primo
  • outros homeworks
  • Prova 2.Z: unicidade
  • princípio da boa ordem e indução forte
  • não par vs ímpar
  • congruência módulo m
  • rem(–,–) e quot(–,–)
  • mod binário vs mod de congruência
  • uso da palavra «módulo»
  • Tô aqui!

18/10/2019: Prova 2.1

21/10/2019: Teoria dos números [video]

  • Correção da Prova 2.1
    • D2. k|n!
    • E1. escolher j de n interios sem nenhum par de consecutivos
    • E2. 5 = 29x + 18y
    • F. consecutivos Fibonacci são coprimos
    • G.
    • I. um critério de gcd
    • Dica: J. o algoritmo de Euclides e Fibonacci
  • Classes e congruência módulo m
  • [a]ₘ
  • três propriedades de congruência módulo m
  • congruência: de ternária para binária
  • reflexividade
  • transitividade
  • simetria
  • os ℤₘ e sua aritmética
  • os nomes dos membros de ℤₘ
  • o que preciso fazer para definir uma operação: tabelas
  • operação «mal-definida»
  • uma outra maneira de pensar sobre a aritmética dos ℤₘ
  • a tabela da adição do ℤ₄
  • um mal-entendido comum
  • a tabela da multiplicação do ℤ₄
  • como inferir comutatividade pela tabela
  • tem x,y com xy = 0 sem nem x=0 nem y=0
  • 2x = 1 tem resolução, ou seja, o 2 tem inverso, ou seja, temos 2⁻¹, ou seja, temos 1/2
  • : numa congruência, podemos cancelar na multiplicação?

23/10/2019: Teoria dos números [video]

  • Correção da Prova 2.1, J: Euclides e Fibonacci
  • Congruências e aritmética modular
  • Tabelas de adição e multiplicação
  • como denotar os objetos de ℤ₂
  • propriedades de adição e multiplicação modular
  • op-identidade
  • op-inverso de número
  • «oposto» (+-inverso) e «inverso» (·-inverso)
  • «quém é» o (-1)?
  • «quém é» o (-k)?
  • comparando quatro «mundos» de aritmética: ℤ, ℤ₅, ℤ₆, ℤ₇
  • inversos
  • zerodivisores
  • cancelamento
  • lei de cancelamento módulo m
  • treta: não podemos esquecer as ferramentas que já demonstramos!
  • O que ganhamos?
  • Corolário: cancelação nos ℤₚ
  • resolução de «equações» e números invertíveis no ℤₘ
  • inversos ⇒ cancelamento
  • de equação para congruência
  • definição «perigosa» e operação «mal-definida»
  • Tô aqui

25/10/2019: Aula cancelada

30/10/2019: Teoria dos números [video]

  • p | C(p,r)?
  • definição «perigosa» e operação «mal-definida»
  • adição
  • multiplicação
  • exponenciação??
  • inversos e cancelamento
  • «único módulo m»
  • Resolução da ax≡b (mod m)
  • Todo composto a possui divisor primo p com p≤√a
  • sistemas de congruências
  • Tô aqui

01/11/2019: Teoria dos números [video]

  • decepção
  • dois exercícios com números consecutivos e módulos
  • qualquer inteiro da forma 3k+2 tem primo divisor da mesma forma
  • «número da forma mk+r»
  • primos da forma 4n+3
  • lembrete: teorema de Euclides
  • teorema de Dirichlet
  • teorema de Fermat
  • o «sonho de calouro»
  • teorema de Fermat: demonstração
  • um sistema de duas congruências
  • como achar inversos
  • únicidade
  • Tô aqui

04/11/2019: Teoria dos números [video]

  • recap
    • teorema de Fermat
    • sonho de calouro
    • Resolução da ax≡b (mod m)
    • sistema de duas congruências x≡bᵢ (mod mᵢ)
  • exemplo com três congruências
  • «dois-a-dois»
  • teorema chinês dos restos
  • correspondência entre k-tuplas de (bᵢ)ᵢ e resoluções (mod M)
  • Critéria de divisibilidade
  • por 3
  • por 9
  • por 11
  • Pensando na aⁿ≡a (mod n)
  • Tô aqui

06/11/2019: Teoria dos números [video]

  • sobre n+1 inteiros entre 1 e 2n
  • princípio de casa do pombo
  • lembrete de homework: eficiência de Euclides
  • Θ. Chinês e uns casos mais gerais
  • Fermat e potências positivas de números módulo m
  • A função φ de Euler
  • 4 teoremas sobre φ
  • φ(pᵃ) = pᵃ-pᵃ⁻¹
  • n ≥ 3 ⇒ φ(n) par
  • Tô aqui

08/11/2019: Teoria dos números [video]

  • eficiência do algoritmo de Euclides
  • Teorema de Fermat e testes de primalidade
  • Um lemma sobre (mod p) e (mod q)
  • x²≡1 (mod p)
  • Θ. Wilson (na vdd Lagrange)
  • Fermat para refutar primalidade
  • exponenciando quadrando repetitivamente
  • Fermat para achar primos
  • φ é multiplicativa: uma dica
  • o converso de Wilson é válido?

11/11/2019: Teoria dos números [video]

  • hipótese chinesa vs primalidade Fermat
  • pseudoprimos
  • sistemas de resíduos
  • φ é multiplicativa
  • como tomar arbitrario membro dum conjunto indexado
  • cuidado: não vale nada concluir coisas a partir do teu alvo
  • cuidado: contrapositivas e justificativas
  • φ é ainda difícil para calcular: fatorização
  • de Fermat para Euler
  • dum exemplo para a segunda demonstração (também de Euler)
  • o exemplo que nos levará para a terceira demonstração foi cortado no vídeo; vou repetir na próxima aula :(
  • Tô aqui

13/11/2019: Teoria dos números [video]

  • números Carmichael
  • 561
  • exponenciação módulo m
  • Lemmata sobre sistemas de residuos
  • O ⇐ de Wilson
  • mentalidade de escuridão
  • fofocas
  • demonstração
  • comprando os critérios de primalidade: Fermat vs Wilson
  • Fermat para computar inversos modulo m
  • choque: logaritmos!
  • ax≡b (mod m)
  • Teorema de Euler
  • dica e investigação com uns exemplos com ajuda por Haskell
  • Tô aqui

18/11/2019: Prova 3.1

20/11/2019: Teoria dos números [video]

  • Correção da Prova 3.1
  • Lema de enganadores de Fermat
  • Teorema de Euler

22/11/2019: Teoria dos números

  • Revisão

27/11/2019: Criptografia [video]

29/11/2019: Criptografia [video]

02/12/2019: Prova 3.2

04/12/2019: Revisão

06/12/2019: Prova de reposição

Futuro (fluido)

Sem futuro. O semestre acabou.

Last update: Sun Jan 30 12:12:42 -03 2022