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

Pocket maths: how to compute averages in your head

Pt En < change language Being able to do basic arithmetic calculations in your head is a great skill. Not because it is sexy but because it is useful in your daily life: it can help you check the change you are given when shopping, it can help you know if you will have enough money to pay for your groceries, it can help you estimate how much things cost after the discounts, etc... This often reduces to being able to sum and subtract decently; sometimes you need to make a couple of small multiplications, but that is it. More likely than not, you don't need to compute averages every day. But sometimes you just want the scoring average of your team for the past few games, or the average price per person of a given meal, or the average time you spent stuck in traffic this past week... And averages may appear nastier than simply adding or subtracting, because averages also require you to perform a division: in fact, you have to add all the numbers you want and then d
Read more

Markov Decision Processes 02: how the discount factor works

Image
Pt En < change language In this previous post I defined a Markov Decision Process and explained all of its components; now, we will be exploring what the discount factor $\gamma$ really is and how it influences the MDP. Let us start with the complete example of last post: In this MDP the states are Hungry and Thirsty (which we will represent with $H$ and $T$) and the actions are Eat and Drink (which we will represent with $E$ and $D$). The transition probabilities are specified by the numbers on top of the arrows. In the previous post we put forward that the best policy for this MDP was defined as $$\begin{cases} \pi(H) = E\\ \pi(T) = D\end{cases}$$ but I didn't really prove that. I will do that in a second, but first what are all the other possible policies? Well, recall that the policy $\pi$ is the "best strategy" to be followed, and $\pi$ is formally seen as a function from the states to the actions, i.e. $\pi: S \to A$. Because of that, we m
Read more