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

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
  • (see also: lipograma, La Disparition, Oulipo)
• 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