Twitter proof: infinite primes


The proof of this post is a very well known proof on the infinitude of primes. For the proof I am going to rephrase an argument used by Euclid more than $2000$ years ago.

Theorem: there are infinitely many primes.

Twitter proof: if $\mathcal{P} = \{p_1, \cdots, p_n\}$ is a finite set of primes, then the number $q = p_1\times\cdots\times p_n + 1$ is such that $q \not\in \mathcal{P}$. Either $q$ is prime or $q$ has a prime factor $q'$ that cannot be in $\mathcal{P}$, otherwise $q'$ would have to divide $1$. Hence, no finite set $\mathcal{P}$ can contain all primes.

A prova deste post é uma prova conhecida da infinitude dos números primos. Para esta prova vou adaptar ligeiramente o argumento usado por Euclides há mais de $2000$ anos.

Teorema: há infinitos números primos.

Prova num tweet: se $\mathcal{P} = \{p_1,\cdots,p_n\}$ é um conjunto finito de primos, então o número $q = p_1\times\cdots\times p_n + 1$ é tal que $q \not \in \mathcal{P}$. Ou $q$ é primo ou $q$ tem um fator primo $q'$ que não pode estar em $\mathcal{P}$, porque se estivesse $q'$ tinha de ser um divisor de $1$. Em qualquer um dos casos concluímos que nenhum conjunto finito $\mathcal{P}$ pode ter todos os primos.

  - RGS

Popular posts from this blog

Tutorial on programming a memory card game

Image
Pt En Este post vai ser um tutorial, não muito detalhado, sobre como fazer um jogo de memória com Python e pygame. O jogo que vamos implementar é um jogo comum: viramos uma série de cartas para baixo e temos que as virar duas a duas, tentando encontrar os pares. Claro que quando viramos duas cartas que não são um par, temos de as voltar de novo para baixo. Quando estou a criar um jogo, gosto de o ir desenvolvendo por etapas funcionais: partir o processo em várias fases que representem pontos nos quais eu tenho algo que posso testar. Deste modo, não só o processo se torna muito mais interessante, como posso ir controlando o aspeto do que estou a produzir. Deixo de seguida uma lista das etapas que eu pensei para este projeto; cada ponto da lista descreve a funcionalidade que o jogo já suporta: Criar um ecrã onde mostro todas as cartas dispostas, face para baixo; Clicar em cima de uma carta faz com que ela se vire para cima; Clicar na segunda carta verifica se encontrei
Read more

Markov Decision Processes 01: the basics

Image
Pt En < change language In this post I will introduce Markov Decision Processes, a common tool used in Reinforcement Learning, a branch of Machine Learning. By the end of the post you will be able to make some sense of the figure above! I will couple the formal details, definitions and maths with an intuitive example that will accompany us throughout this post. In later posts we will make our example more complete and use other examples to explain other properties and characteristics of the MDPs. Let me introduce the context of the example: From a simplistic point of view, I only have two moods: " hungry " and " thirsty ". Thankfully, my parents taught me how to eat and how to drink, so that I can fulfill the needs I mentioned earlier. Of course that eating when I am hungry makes me happy, just as drinking when I am thirsty makes me happy! Not only that, but eating when I am hungry usually satisfies me, much like drinking when I am thirsty us
Read more

The hairy ball theorem and why there is no wind (somewhere) on Earth

Image
Pt En < change language What if I told you that right now there is a place on Earth where there is no wind blowing to the sides? None at all! How can I know that? All we need is what is usually called the Hairy Ball Theorem . In less rigorous contexts, one can phrase the Hairy Ball Theorem as such: Theorem (Hairy Ball I): if you have a hairy ball, regardless of the way you comb its hair there will always be a spot where the hair points right up. In this particular image, the hair is pointing up both on the top and on the bottom. More formally, the Hairy Ball Theorem can be formulated like so: Theorem (Hairy Ball II): every continuous vector field over $S^2$ has at least a point where the tangential component is $0$. From this theorem it is actually quite easy to establish our interesting fact! If we think of the wind at the Earth's surface as a continuous vector field, the Hairy Ball Theorem says that there must be a point where the wind isn'
Read more