test

DIVISIBILIDADE, CONGRUÊNCIAS E ARITMÉTICA MÓDULO n
Carlos Gustavo Moreira

 Nível Avançado

INTRODUÇÃO

Este artigo se propõe a ser uma referência sobre os temas citados no título, que aparecem naturalmente em diversos problemas de Matemática elementar, alguns dos quais serão explicitamente tratados aqui. O estilo é mais conciso do que a maioria dos outros artigos desta revista, o que pode tornar a leitura mais difícil, mas não desanime! Procure entender os enunciados das proposições e os problemas resolvidos e buscar sua propria solução para eles, além de pensar nos problemas propostos e enviar-nos suas soluções. Em caso de qualquer dúvida não deixe de escrever-nos.

Seção 1: Divisão euclidiana e o teorema fundamental da aritmética
Os resultados que seguem têm como base o seguinte fato sobre os inteiros: Dados a  Z, b  N* existem q, r  Z com 0  r < b e a = bq + r. Tais q e r estão unicamente determinados. De fato, q = [a/b] e r = a – bq (aqui [x] denota o único inteiro k tal que k  x < k + 1). Como conseqüência temos a

Proposição 0 (Divisão Euclidiana): Dados a  Z, b  Z* existem q, r  Z unicamente determinados tais que 0  r < be a = bq + r 

Definição: Dados dois inteiros a e b , com a  0 dizemos que a divide b (denotamos ab) se existe c inteiro tal que b = ac.

Proposição 1: Dados a, b  Z não ambos nulos existe d  N* tal que da, db e, para todo c  N*, ca, cb  cd. Além disso existem x, y  Z com d = ax + by. (Esse d é chamado o máximo divisor comum entre a e b : d = mdc (a, b). )

Demonstração: Seja A = {k > 0 x, y  Z tais que k = ax + by} e seja d = ax0 + by0 o menor elemento de A. Mostraremos que da. Como d  N*, existem q, r  Z com a = dq + r e 0  r < d. Queremos mostrar que r = 0. De fato, se r > 0, r = a – dq = a (1 – qx0) + b(– qy0)  A, contradizendo o fato de d ser o menor elemento de A. Portanto, r = 0 e a = dq  da. Do mesmo modo prova-se que db. Suponha agora que ca e cb. Então