self study IDMa: Introdução à Demonstração Matemática (teoria dos números inteiros)

Contato:thanos@imd.ufrn.br
Playlist: IDMa
Monitoria/TA: fmc.imd.ufrn.br
Turmas self: ../
Turmas FMC1: /teaching/fmc1

Info

Pré-requisitos

O IntroProof.

Além disso, é necessário que tu tens tempo e vontade para estudar, fazer os trabalhos atribuídos, etc.

(Obs.: estudarler.)

Conteúdo

(Baseados no módulo correspondentes desta proposta.)

Axiomas sobre os inteiros (domínio de integridade bem ordenado). Demonstrações de teoremas pelos axiomas, sobre as operações e as relações de ordem nos inteiros. A relação de divisibilidade e a verificação de suas principais propriedades. Teorema de Euclides sobre infinidade de primos e sua demonstração construtiva. Lema de divisão de Euclides. Números, numerais, dígitos: demonstração que qualquer inteiro $b > 1$, serve como base para um sistema posicional de numerais para inteiros. Lema de Euclides e sua generalização. Teorema Fundamental da Aritmética. mdc e mmc e demonstrações das suas propriedades Algoritmo de Euclides: corretude e terminação Algoritmo estendido de Euclides Demonstração do teorema Fundamental de Aritmética Congruência módulo um inteiro e demonstrações das suas propriedades Aritmética modular e propriedades do ℤ/mℤ. Algumas conjecturas da teoria dos números: o teorema pequeno de Fermat; a função totiente de Euler; o teorema de Euler.

Objetivos de aprendizagem

Neste módulos usamos elementos da teoria dos números inteiros (IDMa) para introduzir o aluno ao pensamento matemático e o processo de definir conceitos, enunciar e demonstrar teoremas. Aproveitamos o desenvolvimento do conteúdo concreto para chegar até os seguintes conceitos fundamentais:

  • congruência e aritmética modular (IDMa)

Familiarizar com a linguagem usada em definições e demonstrações matemáticas: aprender ler e escrever (usar e interpretar corretamente a linguagem matemática, sua nomenclatura e notação). Apreciar a diferença entre intensional e extensional (sobre igualdades e equivalências). Uso de (meta)variáveis em matemática; ocorrência de variável ligada vs livre; α-conversão (renomeamento); substituição de variável por termos; linguagem vs metalinguagem. Introduzir o lado computacional de uma demonstração, como sequência de comandos que alteram o estado de Dados/Alvos. Entender dois lados de matemática: intuitivo e formal. Propriedades da igualdade e seu uso no raciocínio equacional. Aprender como usar e escrever cálculos dentro de uma demonstração. Apreciar a demonstração como justificativa da veracidade de proposições matemáticas (incluindo de proposições como $p\to p$, leis de distributividade, de De Morgan, frequentemente chamadas «leis» de lógica). Aprender para cada um dos ¬,⇒,∨,∧,∃,∀: como introduzi-lo e como eliminá-lo no texto de uma demonstração. Apreciar a lógica construtiva e os usos dos princípios da lógica clássica (terceiro excluído, redução ao absurdo, dupla negação, contrapositivo); apreciar a diferença entre redução ao absurdo e demonstração direta de negação. Desenvolver definições e teorias matemáticas a partir de noções primitivas e axiomas. Familiarizar com definições e demonstrações que envolvem conjuntos, sequências, funções, e relações. Ter um primeiro contato com conjuntos estruturados e estruturas algébricas e as propriedades das suas operações. Entender como e por quê os sistemas posicionais de numerais funcionam.

Bibliografia e referências

Conhece o libgen?

Principal

Auxiliar

  • Birkhoff & Mac Lane (1977): A Survey of Modern Algebra, 4th ed. (Cap: 1)
  • Mendelson (1973): Number Systems and the Foundations of Analysis (Cap: 3)
  • Avigad, Lewis, van Doorn (2017): Logic and Proof (Cap. 19)
  • Tao (2016): Analysis I, 3rd ed. (Cap: B1)
  • Dasgupta, Papadimitriou, Vazirani: Algorithms [DPV]

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

Dicas

Links

Tecnologias & ferramentas

(Instalem e/ou criem uma conta para usar onde necessário.)

  1. PAPEL (um caderno para dedicar à disciplina) e LAPIS/CANETA.
  2. Zulip (leia o FAQ).
  3. O proof assistant Lean para algumas atividades (leia o FAQ).
  4. Git (leia o FAQ).
  5. Muito recomendado mas não necessário: um sistema Unix (veja o minicurso Unix 2019.2).
  6. Muito recomendado mas não necessário: (neo)vim e Emacs.
  7. Pouco de (La)TeX (veja o minicurso TeX 2018.2). Online editor/compilador: Overleaf.

Este módulo (o IDMa) será auxiliado pelo uso do proof assistant Lean.

FAQs

Dynamic content

Provas

Sessões

Leia bem o FAQ sobre hw. Note também que:

  • Homeworks são atribuidos também durante as aulas e no Zulip.
  • Homeworks marcados assim são auxiliares; tente apenas se tu tem resolvido uma parte satisfatória dos outros.

IDMa (1) [video]

  • Especificação × Implementação
  • Os inteiros $(\mathbb Z;0,1,+,-,\cdot)$
  • Axiomas sobre os inteiros
  • Axiomas vs Teoremas

hw

  1. Cap «Os inteiros», «§. Primeiros passos»
  2. Demonstre os teoremas seguintes sobre os inteiros a partir dos axiomas (procure esclarecimentos no Zulip). Tome cuidado com umas das quantificações que deixei implicitas.
    1. unicidade da $(+)$-identidade (0)
    2. unicidade da $(⋅)$-identidade (1)
    3. leis de $(+)$-cancelamento
    4. unicidade dos $(+)$-inversos (opostos)
    5. 0 é um $(⋅)$-anulador: $0⋅x = 0 = x⋅0$
    6. $-(-x) = x$
    7. $(-1)x = -x$
    8. $(-x)y = -(xy) = x(-y)$
    9. $(-x)(-y) = xy$
    10. leis de $(⋅)$-cancelamento
    11. (|) é reflexiva: (∀a)[a | a]
    12. (|) é transitiva: (∀a,b,c)[a | b & b | c ⇒ a | c]
    13. qualquer inteiro divide o 0
    14. tem inteiros que o 0 divide?
    15. os $1$ e $-1$ dividem qualquer inteiro?
    16. d | a & d | b ⇒ d | ax + by
    17. a | b & b | a ⇒ a = b ?

IDMa (2) [video]

  • bom dia / recap
  • Teoremas x axiomas; dependências de demonstrações
  • Q: por que não aparece (=) na estrutura dos inteiros?
  • Q: como rotular teoremas?
  • Sintaxe vs Semântica; convenções sintácticas
  • juxtaposição; notação infixa/postfixa/prefixa
  • arvore sintáctica; parsing; precedência sintáctica de operadores
  • associatividade sintáctica
  • Operações primitivas vs. definidas
  • subtração como operação definida e não primitiva
  • uns numerais para ajudar: 2, 3, …
  • potências com expoentes naturais; convenção sobre associatividade sintáctica da exponenciação
  • Q: igualdade sintáctica vs intensional
  • Q: o parsing se trata de quais operações?
  • Cancelamento multiplicativo
  • Q: qual a associatividade sintáctica da (⇒)?
  • Q: refutação..?
  • Não-zerodivisores.
  • Q: o «ou» é exclusivo?
  • (Plicker) axiomas ou teoremas?
  • A resposta certa; mais teoremas
  • Existência e unicidade; artigo indefinido vs definido; proof by fight club; alternativa conhecendo já um legal

hw

  1. Cap «Os inteiros», até «§. Conjuntos fechados sobre operações»
  2. Demonstre, ainda com os 8 primeiros axiomas (4 aditivos, 3 multiplicativos, e a distributividade) a equivalência entre:
    • (Z-NZD): (∀a,b)[ ab = 0 ⇒ a = 0 ou b = 0 ]
    • (Z-LC): (∀a,b,c)[ ca = cb ⇒ c = 0 ou a = b ]

IDMa (3) [video]

  • Dica sobre como enxergar alvos
  • A utilidade de lemmas sobre unicidade de resolução de equações num incógnito
  • Exemplos: (∀a)[(-1)a = -a]; (∀a)[0a = a]
  • Axioma x Teorema; Noção primitiva x definida
  • Axiomas sobre ordem: duas maneiras de axiomatizar
  • A (≤) nos naturais é definível
  • Conjunto fechado sob operação
  • Notação set-builder (com comprehension)
  • interpretação de (∈)
  • Como tratar um subconjunto como predicado unário
  • 1 é positivo: teorema ou axioma?
  • O módulo (absolute value) |_| : Int → Int
  • Para refletir: a independência duma proposição: indemonstrabilidade e irrefutabilidade

hw

  1. Demonstre que as duas abordagens vistas na aula são equivalentes:
    • (ℤ;0,1,+,-,·,<) + (ZO-Trans) + (ZO-A) + (ZO-M) + (ZO-Tri)
    • (ℤ;0,1,+,-,·,Pos) + (ZP-ACl) + (ZP-MCl) + (ZP-Tri)
  2. Cap «Os inteiros», até «§. Ordem e positividade»

IDMa (4) [video]

  • como definir «ser fechado sob uma operação n-ária (para n=1,2)
  • uma primeira conversa “adulta” sobre conjuntos
  • um preconceito sobre as () na notação f(x)
  • a notação set-builder: como ler e escrever, e como não ler e como não escrever
  • O que significa «_ ∈ { 3x | x ∈ ℤ }»
  • A diferença intensional entre os extensionalmente iguais conjuntos: {x ∈ A | x ∈ B} e {x ∈ B | x ∈ A}
  • o 3ℤ é fechado sob adição e subtração
  • como generalizar para o mℤ
  • Θ. 1 é positivo
  • Como demonstrar a indemonstrabilidade de proposições
  • A indemonstrabilidade do 0 ≠ 1
  • notação infixa x postfixa x prefixa x mixfixa

hw

  1. Considere os inteiros das primeiras aulas, até a especificação (2/5).
    1. Demonstre que o 0≠1 não é demonstrável a partir desses axiomas.
  2. Considere o (A; ♡, κ) com a especificação seguinte, e demonstre que não tem como demonstrar a Comutatividade de (♡), nem como refutá-la.
    • (♡) : A × A → A
    • κ : A
    • (Ass) : (∀a,b,c)[ (a ♡ b) ♡ c = a ♡ (b ♡ c) ]
    • (IdR) : (∀a)[ a ♡ κ = a ]

IDMa (5) [video]

  • Não existe inteiro estritamente entre 0 e 1: teorema ou axioma?
  • Como escrever definições
  • Duas maneiras que uma definição pode ser errada
  • Quando precisamos demonstrar algo para justificar uma definição ou uma notação
  • o mínimo dum conjunto, quando existe é único
  • Umas propriedades do valor absoluto

hw

  1. Até o «§. Valor absoluto»
  2. Π3.1, Π3.2, Π3.3, Π3.4

IDMa (6) [video]

  • um pleno «tal que» é capaz de destruir uma frase e torná-la pior-que-errada
  • Princípio da boa ordem ($\mathbb Z_{>0}$ é bem ordenado)
  • Como usar o PBO na prática
  • Principios de indução como teoremas
  • Princípio da indução para os inteiros: se $S$ é (+1)-fechado e $1 \in S$, então $\mathbb Z_{>0} \subseteq S$
  • Outras versões de PBO e de Indução e como obtê-las “hackeando” as originais
  • Indução com mais que uma base

hw

  1. Usando o princípio da boa ordem (qualquer conjunto não vazio de inteiros positivos possui mínimo) demonstre: não existe inteiro $c$ tal que $0 < c < 1$.
  2. O «não vazio» acima é redundante?
  3. Demonstre que um conjunto vazio é subconjunto de qualquer conjunto.
  4. Demonstre ou refute: «o Ø é bem-ordenado».
  5. Até o primeiro intervalo de problemas.
  6. Demonstre ou refute: «qualquer conjunto de inteiros X finito é bem ordenado».
  7. Escreva os comandos que temos sobre ataques e usos dos conectivos (∧),(∨),(⇒) como regras de inferência.
  8. Demonstre como teorema o princípio da indução.
  9. Demonstre como corolário o princípio da indução com 2 bases.

IDMa (7) [video]

  • uma interpretação geométrica dos inteiros
  • PBO shiftado e demais versões
  • Indução forte (“course-of-values”)
  • Quebrando os inteiros em tijolinhos atômicos usando como cimento: (i) adição; (ii) multiplicação
  • Definição de invertível
  • Definição de irredutível

IDMa (8) [video]

  • O que queremos? (Wishlist)
    • Divisão (quot e rem)
    • algoritmo para calcular os quot e rem
    • definir e justificar sistemas posicionais de numerais
    • mdc e mmc
    • fatorização única (ao menos de coisas sensatas) de inteiros (teorema fundamental de aritmética)
  • O lemma da divisão de Euclides: enunciado
  • Números, numerais, dígitos
  • Expansão e sistemas posicionais
  • Notação Σ de somatórios
  • O logaritmo como tamanho de númerais melhor que o length deles como strings
  • Enunciado do Teorema Fundamental de Aritmética (fatorização única)
  • Explicação intuitiva sobre como sistemas posicionais funcionam
  • generalização da palavra “maior” para outras ordens
  • diagrama Hasse para os $\mathbb{Z}_{\geq 0}$
  • mdc: definição nível coração

IDMa (9) [video]

  • O lemma da divisão de Euclides: esboço de demonstração
  • Esboço de demonstração do teorema dos sistemas posicionais (expansão em base $b$): qualquer inteiro $b>1$ serve como base para um sistema posicional de numerais para inteiros.
  • “mℤ” ⇔ “fechado sob ops”: concretização e esboço
  • Duas maneiras de obter membros arbitrários de um conjunto indexado
  • Esboço do Teorema Fundamental de Aritmética (fatorização única de inteiros)

hw

  1. Resolva em condições de prova as provas seguintes:
    1. Prova 2.X de 2019.2
    2. Prova 2.Y de 2019.2
    3. Prova 2.Z de 2019.2
  2. Resolva em condições tranqüilas as mesmas provas.

IDMa (10) [video]

  • Invertible, Unit, Irreducible
  • Prime
  • m.d.c.
  • Um exemplo: m.d.c. dos 12,18; divs; comdivs
  • Q: como assim um-maior? A: hmm-maior
  • O que acontece se trocar de (|) para (≤)?
  • O que acontece se trocar de direção nas ordens?
  • Q: qual o tipo desse min?
  • Dados a,b, existe mesmo um m.d.c. deles?
  • Como vou escolher o m.d.c. se os comdivs são esses?
  • Θ. Existência de m.d.c.
  • Q: qual o nome da alma que os m.d.c. e o min compartilham?
  • Duas maneiras de obter membro arbitrário de conjunto indexado
  • Q: Como exatamente funciona essa notação set builder?
  • m.d.c. vs m.m.c (teaser de dualidade)
  • mesmo demonstrando a existência, queremos algoritmo e de preferência eficiente

hw

  1. Escreva sozinho a definição de m.d.c.
  2. Troque o que precisa trocar para virar a definição de mínimo.
  3. Troque o que precisa trocar para virar a definição de máximo.
  4. Troque o que precisa trocar para virar a definição de m.m.c.
  5. Dados inteiros a,b, demonstre a existência dum m.d.c. deles, e mostre que ele pode ser escrito como combinação linear dos a,b.
  6. Demonstre as propriedades básicas dum m.d.c., que denotamos aqui simplesmente por (_,_), exceto uma, que é refutável (e logo refute e depois obviamente tente a ajustar para virar demonstrável, e demonstre–phew!):
    1. (a,b) = (a,-b) = (-a,b) = (-a,-b)
    2. (a,a) = ?
    3. (a,0) = ?
    4. (a,1) = ?
    5. (a,b) = (b,a)
    6. ((a,b),c) = ?
    7. (a,b) = (a, a + b)
    8. (a,b) = (a, a - b)
    9. (ca,cb) = c(a,b)
    10. (uv,a) = (u,a)(v,a)
    11. (a,b) = (b, rem(a,b))
  7. Demonstre: Invertible(x) ⇔ Unit(x)
  8. Demonstre: Irreducible(x) ⇔ Prime(x)
  9. Demonstre ou refute: apra quaisquer primos distintos p,q, pq | n² ⇒ pq | n.
  10. 🚀 Bora viajar legal!
    1. Num universo de conjuntos (por exemplo no Set(Int)) considere a mesma definição de m.d.c., mas essa vez usando como guia a ordem de (⊆). Qual conceito definiu? O que acontece se virar as direções? (⊇).
    2. Tendo P, Q : Prop, escrevemos P ⊢ Q para a (meta)proposição «Dado a P, podemos demonstrar a Q.». No universo de proposições, mostre que (⊢) é uma pré-ordem. Qual seria o “m.d.c.” de duas props, e qual o “m.m.c” delas?

Prova 1.3

hw

  1. Troque o (Z-PBO) pelo princípio da indução (Z-Ind). Demonstre o (Z-PBO).

IDMa (11) [video]

  • Como demonstrar (a,b)=(c,d).
  • Algoritmo de Euclides: corretude e terminação
  • Terminação, Corretude, Eficiência
  • Algoritmo estendido de Euclides
  • coprimos

mais hw

  1. 💻 Na aula foi óbvio que ninguém merece fazer contas na mão, mesmo utilizando um algoritmo eficiente. Mas somos programadores—right?—e logo: programe na tua linguagem favorita uma função que dados dois inteiros a, b, retorna seu m.d.c. d, e também coeficientes Bézout x,y tais que d = ax + by. Dica: caso que tua linguagem favorita não seja a Haskell, troque e tente novamente.
  2. L: a ≥ b > 0 ⇒ r < a/2. (Aqui a/2 é o quot(a,2).)
  3. Θ: Para todo n ≥ 1, e quaisquer inteiros a > b > 0, se o algoritmo de Euclide precisa n passos (divisões) para terminar, então a ≥ fib(n+2) e b ≥ fib(n+1), onde fib(i) é o i-ésimo número Fibonacci.

IDMa (12) [video]

  • Algo que parece LEM, mas não é
  • Lema de Euclides e sua generalização
  • Dum lemma para uma ideia: n² (im)par ⇔ n (im)par
  • “unicidade” de m.d.c.
  • Teorema de Euclides sobre infinidade de primos e sua demonstração construtiva
  • sermão sobre x² par ⇒ x par
  • generalizações
  • m.d.c. e os coeficientes Bézout
  • Lemma de Euclides: x irredutível ⇒ x primo
  • Momentos que parecem LEM mas não são
  • Sobre a contaminação de demonstrações com magias ⛤
  • Erdős: «proofs from The Book»
  • Teorema de Euclides: há uma infinidade de primos
  • Como decidir se um inteiro é primo.
  • Sobre Euclides e seus Elementos
  • Sobre o teorema fundamental de aritmética
  • Como codificar listas de inteiros nos inteiros?

hw

  1. Demonstre o que faltou para a demonstração do Lemma de Bézout: p irredutível & p ∤ a ⇒ (p,a) = 1.
  2. Como podemos generalizar o Lemma de Bézout sobre p’s não-necessariamente-irredutíveis?
  3. Demonstre o Teorema Fundamental da Aritmética
  4. Dado as «formas canônicas» de inteiros a e b, descreva os m.d.c. e m.m.c. deles
  5. Demonstre que dado um inteiro x, se não há primos divisores de 2 até ⌊√x⌋, então x é primo

IDMa (13) [video]

  • Correção sobre o «algoritmo da criança» vs «algoritmo de Euclides»
  • Fatorização é lenta
  • Densidade de primos e gaps
  • Algumas conjecturas da teoria dos números: Gêmeos, Goldbach, Collatz, Legendre
  • O enunciado do teorema dos números primos (PNT)
  • O enunciado do teorema Chebyshev (postulado de Bertrand)
  • Congruência módulo um inteiro e demonstrações das suas propriedades
  • Aritmética modular e propriedades do $\mathbb Z / m\mathbb Z$
  • (·)-inversos módulo um inteiro m

hw

  1. Seja n > 0. Ache n inteiros consecutivos tais que nenhum deles é primo.
  2. Seja m inteiro. Demonstre que (≡ₘ) é uma relação de equivalência: (i) reflexiva; (ii) transitiva; (iii) simétrica
  3. Seja m inteiro. Demonstre que (≡ₘ) é uma congruência para a estrutura (ℤ; 0, 1, +, ·, -), ou seja, que é compatível com essa estrutura, ou seja, que:
    1. a ≡ₘ a’ & b ≡ₘ b’ ⇒ a + b ≡ₘ a’ + b’
    2. a ≡ₘ a’ & b ≡ₘ b’ ⇒ a · b ≡ₘ a’ · b’
    3. a ≡ₘ a’ ⇒ -a ≡ₘ -a’
  4. Seja m inteiro. Demonstre ou refute, se puder:
    1. a ≡ₘ b ⇒ a + x ≡ₘ b + x
    2. a ≡ₘ b ⇒ a · x ≡ₘ b · x
    3. a ≡ₘ b ⇒ -a ≡ₘ -b
    4. a ≡ₘ b ⇒ aˣ ≡ₘ bˣ
  5. O «planeta 1» faz sentido? Como é?
  6. O «planeta 0» faz sentido? Como é?
  7. Demonstre o que consegues da equivalência das duas sugestões do que deveria significar o a ≡ₘ b.

IDMa (14) [video]

  • por que as duas definições de congruência não são mesmo equivalentes
  • o planeta 0: a terra
  • o planeta 1: o {⋆}
  • as notações mA e A+k e os mℤ, mℤ+k
  • Aritmética módular, pouco mais adulta
  • Θ: Invertibilidade módulo m
  • D: Congruência, compatibilidade com operações
  • Θ: Unicidade de inversos módulo m
  • Critéria de divisibilidade
  • O Teorema Fundamental de Aritmética para os racionais
  • Sobre um sistema de resíduos módulo p
  • Plicker: «Existem quantos planetas onde todos os não nulos são invertíveis?»

hw

  1. Sejam $a$ inteiro e $p$ primo tais que $(a,p) = 1$. Seja $R_p = \{0,1, \dotsc, p-1\}$. Demonstre que $aR_p$ possui exatamente um representante de cada classe (time).
  2. $a$ invertível módulo $m$ sse (a,m) = 1.
  3. Unicidade de inversos módulo $m$.
  4. Mostre que a (≡ₘ) não é compatível com a exponenciação.
  5. Elabore e justifique critério de divisibilidade para os 2,3,4,5,9,11

mais hw

  1. Encontre um inverso de 18, módulo 125.
  2. Encontre inteiro x tal que $6^{1032} \equiv x \pmod {11}$.
  3. Dados inteiros $a,b,m$ quantas multiplicações tu precisa fazer para achar um inteiro $x$ tal que $a^b \equiv x \pmod m$?
  4. Querendo escrever um guia para alunos (ou maquinas!) saber como resolver congruências e sistemas de congruências, o que tu escreveria sobre:
    1. $\phantom a x \equiv b \pmod m$
    2. $ax \equiv 1 \pmod m$
    3. $ax \equiv b \pmod m$
    4. Um sistema de $n$ congruências $x \equiv b_i \pmod {m_i}$. (Dica: resolva primeiro para o caso $n = 2$.)
  5. Demonstre que existe uma infinidade de primos «da forma 4n+3».
  6. Depois de resolver o problema anterior, explique por que sua resolução não é adaptável para primos «da forma 4n+1».
  7. Demonstre: p primo ⇔ (p-1)! ≡ -1 (mod p).

IDMa (15) [video]

  • Decepção de falta de hw
    • Achando inversos modulares
    • Exponenciação modular
    • Resolvendo congruências
    • Resolvendo sistemas de congruências
    • Θ. infinidade de primos da forma 4k+1 e da forma 4k+3
    • Θ. teorema de Wilson
  • Ferramentas até agora: rápidos vs lentos
  • Pouco de análise combinatória
  • Θ. Teorema pequeno de Fermat: enunciado
  • Teorema e coeficientes de binomial
  • Θ. O sonho do calouro
  • $p$ divide o $C(p,i)$ para $0 < i < p$

hw

  1. Demonstre o «sonho do calouro»: Para qualquer primo $p$, $(x + y)^p \equiv x^p + y^p \pmod p$.
  2. Demonstre por indução o teorema binomial: $(x + y)^n = \sum_{i=0}^n {n \choose i} x^iy^{n-i}$, onde ${n \choose r} = C(n,r)$.
  3. Demonstre que $(\forall 0 < i < p)[p \mid C(p,i)]$.
  4. Consiga como corolario desses teoremas o «Teorema pequeno de Fermat»: $a^p \equiv a \pmod p$.
  5. AINDA?!: Sejam $a$ inteiro e $p$ primo tais que $(a,p) = 1$. Seja $R_p = \{0,1, \dotsc, p-1\}$. Demonstre que $aR_p$ possui exatamente um representante de cada classe (time). [foi postado 10 dias atrás].
  6. Ache a pior entrada para euclides e justifique tua resposta.
  7. Termine a implementação recursiva do $C({-},{-})$.
  8. Demonstre que $C(n,r) = \dfrac {n!}{r! (n-r)!}$.
  9. Sejam n,r inteiros. Demonstre: $r! (n-r)! \mid n!$.
  10. As duas métodos que descrevemos sobre a resolução de $ax \equiv 1 \pmod m$ e de $ax \equiv b \pmod m$ em algum ponto mandaram checar se $a,m$ são coprimos. Caso que não são, podemos concluir que tais congruências não possuem resolução?
  11. Infira o “princípio” multiplicativo de contagem a partir do princípio aditivo.

IDMa (16) [video]

  • Θ. Teorema binomial
  • Θ. O sonho do calouro
  • Θ. “Fermatinho” de Fermat (demonstração de Euler, por indução)
  • A hipotese (errada) “chinesa”
  • Enganadores do Fermatinho: Carmichael
  • Teste de primalidade de Fermat
  • Se tem ilegais, pelo menos a metade é ilegal
  • Como gerar primos
  • Sistemas de resíduos módulo m: completos e reduzidos
  • A função totiente de Euler

hw

  1. Seja $R_m = \{r_1,\dotsc,r_{\varphi(m)}\}$ é um sistema reduzido de resíduos módulo $m$. Demonstre:
    1. Se (a,m)=1, então aRₘ também é um s.r.r. módulo m.
    2. $\sum_{r\in R_m} r \equiv 0 \pmod m$.
    3. Rₘ é (·)-“fechado módulo m”.
    4. (∀r ∈ Rₘ)(∀x ∈ ℤ)(∃u ∈ ℤ)[ x ≡ₘ ru ]
  2. (qm + r, m) = (r,m)
  3. (a,nm) = 1 ⇔ (a,m) = 1 & (a,n) = 1
  4. φ(p) = p-1
  5. φ(pᵏ) = pᵏ - pᵏ⁻¹
  6. Calcule um dos φ(2), φ(3), φ(4), …, φ(13)
  7. φ é multiplicativa, ou seja: (m,n)=1 ⇒ φ(mn) = φ(m) φ(n). Dica: escreva todos os números de 1 até mn numa tabela de m × n.
  8. Calcule de novo, essa vez todos os φ(2), φ(3), φ(4), …, φ(13). (Não se engane: fatorização demora!)
  9. φ(n) é par para qualquer n > 2.
  10. Calcule o valor do somatório $\sum_{i=0}^k \varphi(p^i)$.
  11. $a^{\varphi(m)} \mathrel{\equiv_m} 1 \iff (a,m) = 1$. Dica: φ e sistemas reduzidos de resíduos são intimamente relacionados, né?
  12. Mostre que o Fermatinho é um corolário da proposição anterior!
  13. Seja $p$ primo e defina a função $V_p : \mathsf{Int} \to \mathsf{Int}$ pelas:
    $V_p~a = \max\{ i\;\mid\; p^i \mid a\}$ para $a \neq 0$ e para $a = 0$, decida tu!
    Demonstre:
    1. V (a+b) ≥ min (V a) (V b)
    2. V (ab) = V a + V b
    3. V (a,b) = min (V a) (V b)
    4. V [a,b] = max (V a) (V b)
    5. Defina $\Vert a \Vert_p = p^{- (V_p\,a)}$. Demonstre: $$ \begin{gathered} \Vert ab \Vert = \Vert a \Vert \, \Vert b \Vert \\ \Vert a + b\Vert \leq \max \{\Vert a \Vert, \Vert b \Vert \} \leq \Vert a \Vert + \Vert b \Vert \\ \prod_{p~\text{primo}} \Vert a \Vert_p = \frac 1 {|a|} \\ \end{gathered} $$

IDMa (17) [video]

  • p-valuações, tamanho e distância p-adica
  • raizes quadradas e resíduos quadráticos módulo p
  • Euler entra!
  • Umas aplicações da teoria dos números inteiros
  • Sobre criptografia
  • Criptografia vs steganografia
  • Cæsar, rot13
  • one-time pad
  • Plicker survey

IDMa (18) [video]

  • φ(pᵃ) = pᵃ - pᵃ⁻¹
  • φ é multiplicativa
  • criptografia RSA
  • assinaturas digitais: objetivo

hw

  1. Demonstre, depois do esboço/dica da aula: φ é multiplicativa.
  2. Demonstramos a propriedade principal de descryptografar, mas nela a gente supôs que $m,N$ são coprimos. Temos mesmo como garantir isso? Se sim, por quê? Se não, o que acontece se por sorte (i.e., azar) a mensagem $m$ que queremos mandar não é coprima com o $N$?
  3. Considere que temos acesso numa função $h : D \to H$ que dada um valor de informação $d \in D$, retorna o seu hash $h(d) \in H$. Suponha que ela, mesmo sendo conhecida por todos, tem a propriedade seguinte: dado um $s \in H$, é difícil achar um valor $d_s \in D$ tal que $h(d_s) = s$. Pense numa maneira de usar o sistema RSA que a gente discutiu na aula para conseguir assinaturas digitais: queremos uma maneira de ter certeza que a mensagem que recebemos supostamente escritar por Alice, foi escrita por Alice mesmo. Dica 1. Temos que $e$ é um inverso de $d$, e logo $d$ é um inverso de $e$ também. Observem que $(m^e)^d=(m^d)^e$. Dica 2. A chave privada deve ser usada para trancar(cryptografar) algo, que qualquer pessoa pode destrancar(descryptografar) mas apenas quem está em posse da chave privada poderia ter sido o trancador.

Prova 1.4

Em um universo paralelo

  • Universal hash
  • Assinatura digital
  • Um toque de álgebra abstrata

Last update: Mon Sep 25 09:00:21 -03 2023