Contraprova visual do Pequeno Teorema de Fermat

Em post anterior, vimos uma prova visual do Pequeno Teorema de Fermat.

Neste post, vamos ilustrar o mesmo raciocínio, mas para mostrar porque o mesmo teorema não funciona quando os números envolvidos não são primos entre si.

O teorema diz que p | n^p – n, para p primo.

Exemplo. n = 3 e p = 5.
n^p – n = 3^5 – 3 = 240, e 240 é divisível por 5.

Contra exemplo. n = 2 e p = 4.
n^p – n = 2^4 – 2 = 14, e 14 não é divisível por 4 (para o teorema funcionar, p deve ser primo em relação a n).

Vamos visualizar o caso n =2 e p =4.

Há duas combinações de cor única:

Há quatro combinações com 1 azul e 3 brancos. Note o mesmo comportamento descrito anteriormente, de poder fazer um colar e ir girando a cada conta. A repetição só se dá quando girar todas as contas.

De modo similar, há quatro combinações com 3 azuis e 1 branco.

Porém, com 2 azuis e 2 brancos, há uma diferença.

O primeiro grupo de 4 forma um colar que precisa de 4 giros para retornar ao início.

Porém, o grupo da direita precisa de apenas 2 giros para retornar à mesma posição. Isso porque há repetição do padrão de cores, e há repetição porque 2 (cores) e 4 (posições) têm divisor comum (2).

Isso “quebra” a formação de grupos de 4, demonstrando o motivo do pequeno Teorema de Fermat não ser válido para n e p com divisores comuns.

Portanto, essa é a forma de visualizar o importante Pequeno Teorema de Fermat.

Veja também:

Prova visual do Pequeno Teorema de Fermat

O Pequeno Teorema de Fermat é uma das joias da Teoria dos Números, e é utilizada, por exemplo, em testes de primalidade para a criptografia moderna.

Ela diz que p | n^p – n, para p primo.

Exemplo. n = 3 e p = 5.
n^p – n = 3^5 – 3 = 240, e 240 é divisível por 5.

Exemplo. n = 4 e p = 3.
n^p – n = 4^3 – 4 = 60, e 60 é divisível por 3.

Contra exemplo. n = 2 e p = 4.
n^p – n = 2^4 – 2 = 14, e 14 não é divisível por 4 (para o teorema funcionar, p deve ser primo em relação a n).

Não confundir com o Grande Teorema de Fermat, aquele que ficou famoso por demorar 300 anos para ser resolvido. O matemático Pierre de Fermat dizia ter a prova na cabeça, mas não cabia no rodapé do livro que ele estava anotando.

O Pequeno Teorema de Fermat tem uma prova combinatória / visualização muito bonita.

A primeira observação é que n^p é uma fórmula muito conhecida em análise combinatória.
Por exemplo, se p=3 posições (as três bolinhas abaixo) e n = 4 cores, n^p indica o número de combinações de cores para pintar as três bolinhas de forma diferente (onde a ordem importa).

A segunda observação. Há n = 4 cores únicas, então se eu pintar as p = 3 bolinhas apenas com uma cor, tenho 4 possibilidades.

Assim, n^p – n = 4^3 – 4 = 60 combinações possíveis de todas as cores para pintar 3 bolinhas, tirando as cores únicas.

Vamos ver as combinações de duas cores. Há 36 formas de colorir as três contas, usando as 4 cores combinadas duas a duas.

O argumento aqui é que, naturalmente, as cores se juntam em grupos de tamanho p.

Imagine cada coluna como se fosse um colar. Se eu amarrar o topo da linha com a base, tenho um círculo. Tenho que girar cada conta p vezes para ela se repetir, porque p é primo entre si com n – não vai haver uma combinação da mesma cor sem girar p posições.

Para combinações de três cores, vide esquema abaixo.


Há 24 formas de colorir as três contas, usando as 4 cores combinadas três a três.

Portanto 24 combinações 3 a 3, mais 36 combinações 2 a 2, mais 4 combinações únicas dá 64 combinações possíveis (igual a 4^3). Tirando as 4 combinações únicas, as outras combinações naturalmente formam grupos de periodicidade p = 3.

Em post seguinte, vou mostrar um contra-exemplo visual, para ilustrar como dois números divisíveis entre si provocam uma repetição, e assim as combinações não se agrupam naturalmente em múltiplos de p.

Trilha sonora: Louis Armstrong – What a Wonderful World

Código fonte do desenho das bolinhas no Github: https://github.com/asgunzi/Prova-Visual-Pequeno-Teor-Fermat

Veja também:

Arábia Saudita – o Poder da Geografia

Minhas notas, capítulo sobre a Arábia Saudita, do livro “O Poder da Geografia”, de Tim Marshall.

O nome do país é composto de duas partes, Arábia e Saudita.

Saud é o nome de uma família, que controlava uma região menor. A região foi vastamente expandida há uma centena de anos. Se o país é o nome de uma família, o que acontece a quem não é da Casa de Saud?

Os Saudis fazem a política, e outro grupo, Wahabis, a religião. Ambos expandiram região de influência, agregandos outros emirados menores. Isso explica a tensão que existe atualmente.

Atualmente, há 34 milhões de pessoas, religião islâmica sunita.

A Arábia Saudita cobre grande parte da península arábica. Não há muito mais do que petróleo e areia. É uma área desértica, que chega a 50 graus na sombra. É o país com a maior extensão do mundo sem um rio. Terras altas a leste, onde ficam cidades mais importantes. Ao sul, montanhas.

Nos anos 1700, a família Saud transformou o berço do estado saudita em um mercado florescente, ganhando força regional.

Fizeram um pacto com o clã Wahab. Saud domina a política, Wahab, a religião.

Para cimentar relações, casamentos.

A aliança foi se expandindo, conquistando outras regiões.

É uma das sociedades mais restritas do mundo moderno.

Perderam controle após invasão dos otomanos, em 1818. O reinado foi destruído, e foi sendo reconstruído até a retomada de Riad, em 1824.

Outra ponto baixo foi em 1890, ao perder o controle de Riad, para família Rashid. Desapareceriam da história, não fosse Abdulaziz bin Abdul Rahman Al Saud. Em 1901, sucedeu o pai, como líder da família Saud. Depois, liderou a reconquista da região e fundou o estado da Arábia Saudita em 1932.

Após a descoberta de óleo, acordos com britânicos garantiram a posição dos Saud.

Ele também arranjou casamentos com representante de todos emirados, da onde nasceram centenas de filhos, e uma rede de familiares que domina a região até hoje.

Na época da Segunda Guerra, os sauditas fizeram um acordo com os EUA. Os EUA teriam acesso ao petróleo, e a Arábia Saudita teria apoio americano para garantir as fronteiras.

Após uma rebelião com a tomada de um mosteiro em 1979, houve um encrudescimento em ativismo religioso. Aumento da participação da religião, wahabismo reforçado, mulheres com menor participação na vida social.

O petróleo financia um enorme estado de bem estar social. O óleo fundamenta as relações modernas da Arábia Saudita.

Há uma preocupação enorme no que fazer após o petróleo.

Alguns projetos incluem uma cidade autônoma, para 2030. Diversificação de investimentos: investem em startups, como a Tesla.

O maior consumo de energia é com ar condicionado. Estimativa de ser responsável por 70 por cento da energia.

Estimativa de 4/5 de uso da água, que deve acabamos em 2030. Óleo subsidia, mas sem água não tem como. Plantas de dessalinização precisam de muita energia. O fundo soberano está comprando áreas em outros países.

Como investir equilibrando os polpudos subsídios de hoje?

O que será da Arabia saudita quando acabar o petróleo?

Links da Amazon:

O Poder da Geografia https://amzn.to/2XpbO6l

Prisioneiros da Geografia https://amzn.to/3CrmOzf

O Poder da Geografia – Irã

Minhas notas do capítulo sobre o Irã, do livro “O Poder da Geografia”, de Tim Marshall.

Na história, o Irã sempre foi conhecido como Pérsia, mas foi renomeada em 1935 para tentar representar minorias não persas.

Formado por áreas montanhosas e desérticas.

Persas são a maioria da população, mas há curdos, azerbaijãos, armênios, árabes e outras minorias.

Tendência a ter governo central forte para reprimir esses vários grupos.

Sobre área desértica, outra característica é a falta de água. Há apenas um rio navegável.

O Irã possui a quarta reserva de óleo do mundo. Porém, os equipamentos existentes são extremamente ineficientes, com a dificuldade adicional de existirem sanções internacionais ao país.

A energia, petróleo, é a principal produto de exportação.

O Irã atual é cheio de problemas, mas a sua história é gloriosa. A Pérsia era uma nação líder em tempos antigos.

O primeiro império persa envolveu figuras como Ciro, Dário e Xerxes, que provocaram guerras com a Grécia.

Depois disso, houve uma série de invasores, alternando impérios persas. Alexandre, o Grande. Roma. Mongóis de Gênghis Khan. Tamerlão. Turcos otomanos. Russos. Britânicos.

Após a descoberta de óleo, na Primeira Guerra, os britânicos se asseguraram de que teriam preferência para exploração, o que levou a várias trocas de poder no local – e foi essa a época da troca do nome para Irã.

Depois da Segunda Guerra, russos e britânicos exploraram a região, assegurando o óleo.

Na época da Guerra Fria, os EUA e britânicos ajudaram uma das facções iranianas a chegar ao poder, temendo que este se tornasse um país comunista.

Na revolução que ocorreu em 1979, o Aiatolá Khomeini chegou ao poder, perseguindo adversários, minorias, tolhendo liberdades.

Após a revolução, os EUA deram preferência ao Iraque, criando um estado xiita à leste do Irã (que é sunita).

A guerra Irã-Iraque, nos anos 80, durou 8 anos, 1 milhão de mortes e terminou sem alterar nada.

Após a morte de Khomeini, os sucessores continuaram a governar com mão de ferro.

Mais atualmente, o presidente Mahmoud Ahmadinejad continuou turbulência política. Aumento de isolamento e piora econômica.

Nos últimos 40 anos, também é relevante citar o desprezo a judeus e a Israel.

Atualmente, a economia continua afundando, com inflação e desemprego em alta.

Links da Amazon:

O Poder da Geografia https://amzn.to/2XpbO6l

Prisioneiros da Geografia https://amzn.to/3CrmOzf

Os fracassos de Papanicolau até o exame que leva o seu nome

Poucos cientistas estudaram a fase inicial do câncer tão intensivamente quanto George Papanicolau.
Ele era um médico grego, quando chegou aos EUA em 1913, sem um centavo no bolso.

Papanicolau foi levando a vida como vendedor de carpetes, antes de conseguir uma posição na Universidade de Cornell, NY.

Mas mesmo em Cornell, era para uma tarefa menor. Estudar ciclo menstrual de porquinhos da Índia, uma espécie que não sangra nem apresenta outros sinais evidentes na menstruação.

Ele aprendeu a extrair células uterinas e analisar as suas formas. Sabendo a morfologia das células, ele conseguia dizer a posição do ciclo menstrual.

A seguir, ele expandiu o estudo para pacientes humanos. O método também funcionava em seres humanos, porém era uma invenção inútil. Faz séculos que mulheres sabem os seus ciclos, sem ajuda do método de Papanicolau.

Sem se abalar com as críticas, o médico continuou pesquisando, coletando tudo quanto era amostra de doenças ginecológicas – fibróides, cistos, tubérculos, inflamações.

O câncer, ele descobriu, tinha tendência de criar formas anormais, aberrantes.

Entusiasmado, ele publicou o artigo com a descoberta em 1928, apenas para sofrer mais críticas. O método não era muito acurado nem sensitivo. E havia outras formas de detectar câncer cervical.

Após duas invenções inúteis em 20 anos, ele desapareceu por um tempo.

Entre 1928 e 1950, Papanicolau voltou ao tema com ferocidade.

Será que o câncer também não muda a morfologia com o tempo?

Ele e colaboradores adaptaram o método não para detectar o câncer, mas sim, o pré-câncer.

Em 1952, ele conseguiu convencer o Instituto Nacional do Câncer a realizar o maior teste da história, utilizando o seu método. 150 mil mulheres fizeram o teste de Papanicolau. Encontraram câncer invasivo em 555 casos. Se não tivessem sido testadas, não teriam sabido, pois não havia sintomas. E as mulheres testadas estavam numa idade 20 anos a menos que a idade média de casos.

Papanicolau transformou um caso de câncer virtualmente incurável em curável, e o seu teste é o padrão mundial utilizado até hoje.

Lição da história. Não desistir após resultados negativos.

Fonte: “O imperador de todos os males”, Siddhartha Mukherjee.

Link da Amazon: https://amzn.to/3i1WWSM

Divulgando iniciativa dos amigos da BR Quantum

Fontes – Advanced Analytics e AI

Compartilhando algumas boas fontes de Advanced Analytics e AI que utilizo, e solicito ajuda de vocês, para indicar outros links legais e pessoas a seguir.

O Exponential View envia um newsletter com gráficos extremamente bonitos e análises diversas.
https://www.exponentialview.co/

Na plataforma Medium, é possível ler e escrever sobre temas de interesse. Esses artigos são reunidos em revistas, com uma excelente curadoria de conteúdo. https://medium.com/

John D. Cook tem um blog e twitter de alto nível, sobre matemática e programação https://www.johndcook.com/blog/

Instituições: A brasileira SOBRAPO (https://sobrapo.org.br/) e a americana Informs (https://www.informs.org/) são referência em eventos e publicações de Pesquisa Operacional, um pouco mais tradicionais. Já a Association For The Advancement Of Artificial Intelligence é voltada à IA https://www.aaai.org/.

Sobre Quantum computing:

Para fechar, é claro, sigam o meu blog de Ideias Técnicas com uma pitada de filosofia: https://ideiasesquecidas.com/

Fiquem à vontade para sugerir outras fontes.

O Poder da Geografia – Austrália

Para os amigos que se interessam por Geografia e História, uma recomendação: “O Poder da Geografia”, de Tim Marshall, um dos maiores especialistas do mundo sobre o tema.

Neste livro, ele aborda a Austrália, Sahel, Grécia, Turquia, UK, Irã, Etiópia, Arábia Saudita, Espanha e o Espaço.

Segue um pequeno resumo sobre a Austrália.

A Austrália foi de lugar nenhum para ponto estratégico na história.

Perto da China, acesso aos EUA e ao Oceano Pacífico.

De ilha de prisioneiros a nação de primeiro mundo, multicultural.

Área desértica ocupa mais de 70 por cento da ilha. Todos os rios juntos tem vazão menor que Yang Tsé, por exemplo.

Sobre ondas de imigração. A primeira carga de prisioneiros chegou em 1788. Muitos brancos britânicos, depois aceitação maior de outros habitantes. A corrida do ouro ajudou a aumentar a imigração. Hoje, aumento da participação de asiáticos, como chineses, até pela proximidade.

A Austrália está sofrendo com mudanças climáticas. Seca, propensão a incêndios florestais, como um que ocorreu em 2009, piorando a poluição do ar.

Para piorar o impacto ambiental, a tendência é ir de 25 para 40 milhões de habitantes no futuro.

Sobre energia. Por ser muito plano, não há potência hídrica. Mas há abundância de carvão, que é uma indústria importante. Porém, isso agrava problemas climáticos.

Há diversos grupos de aborígenes. Desde as primeiras colônias, houve aniquilação de aborígenes, que mal eram considerados humanos, luta que continua até hoje.

A Austrália sempre se aliou a potências. UK. EUA. Agora, ascensão da China. Estudantes chineses na Austrália, são mais de 30 por cento do total. 1/3 das exportações são para a China. O futuro da Austrália pode ser cada vez mais chinês.

Links da Amazon:

O Poder da Geografia https://amzn.to/2XpbO6l

Prisioneiros da Geografia https://amzn.to/3CrmOzf

Senos de inteiros

Padrões interessantes surgem, quando plotamos a função seno para números inteiros [sin(1), sin(2), sin(3), …, sin(N)].

Painel interativo aqui:
https://asgunzi.github.io/Senos-inteiros/index.html

Para N = 500, aparecem alguns hexágonos.

Para N = 1000, fica mais evidente.

Para N = 2000:

Para N= 5000:

A mesma coisa, mas com o eixo X em escala logarítmica.

Achei bonito o padrão formado, e resolvi fazer os gráficos.

Este post é baseado em artigo de John Cook, referenciado abaixo.

Veja também:

O time de 1 bilhão de euros e o funil estreito

Pep Guardiola é o técnico do Manchester City, time avaliado em 1 bilhão de euros. (Obs. 1 libra = 1,17 euros).

https://www.uol.com.br/esporte/futebol/ultimas-noticias/2021/08/17/city-lidera-lista-de-clubes-com-os-elencos-mais-valiosos-psg-e-o-3.htm

Já ouvi comentários do tipo: “com 1 bilhão de euros, até eu sou técnico”. Isso pode até ser verdade, um time desses joga praticamente sozinho. Porém, a pergunta de verdade a se fazer é exatamente a contrária.

Imagine o grupo de acionistas de um patrimônio tão enorme. A quem eles confiaram o comando do time? A um aventureiro qualquer? Ao Joel Santana? Ou ao Guardiola? Obviamente, o escolhido será quem já provou entregar resultados em alto nível.

É o mesmo para CEO de grandes empresas, posições importantes, etc…

Porém, isso cria um funil estreito: só tem a posição quem já entregou resultados, porém, para entregar resultados é preciso ter a posição.

Como o funil é estreito, salários e atenção da mídia tendem a focar nesses superstars, embora sempre haja uma equipe grande e talentosa “jogando sozinha”. Quanto mais estreito o funil, maior o destaque, é um efeito do tipo power law, o vencedor-leva-tudo.

É por isso que Guardiola é o técnico do time mais valioso do mundo, e não um aventureiro qualquer.

Veja também:

Prova visual da aproximação de raiz (a + b)

A expressão a seguir fornece uma aproximação da raiz (a + b), quando b<<a (b muito menor que a):

Dá para interpretar facilmente a aproximação, pensando em áreas.

A raiz quadrada de a é o lado do quadrado que tem área a.

Suponha que queremos a raiz de a + b, e o quadrado a seguir tenha exatamente as dimensões desejadas.

Como fazer para encontrar o valor desconhecido x?

Se a área verde é igual a b, metade dela será b/2, e essa área é aproximadamente igual a raiz(a) * x, desprezando a “quina” que não faz parte do retângulo.

Assim, temos x = b/(2*raiz(a)), e a dedução da fórmula citada.

Note que o erro equivale à parte em vermelho do diagrama.

E o erro será menor tanto quanto b for menor do que a.

Veja também:

https://ideiasesquecidas.com/laboratorio-de-matematica

Números Triangulares

Números triangulares são aqueles que formam um triângulo, fazendo jus ao próprio nome.

1

3 = 1 +2

6 = 1 +2 + 3

10 = 1 +2 + 3 + 4

Fiz uma animaçãozinha para demonstrar. Para visualização interativa: https://asgunzi.github.io/NumerosTriangulares/

Cada número triangular é a soma da progressão geométrica 1+2+3+…+N, ou seja, podemos usar a fórmula da PG para calcular um número triangular qualquer.

Vide também: