Escreva um programa em
que encontre o menor inteiro positivo
que atenda as seguintes condições :
inteiro e resto 2
inteiro e resto 3
inteiro e resto 4
Passo 1
O enunciado pede: escrever um programa em
que encontre o menor inteiro positivo
que satisfaça simultaneamente as três condições abaixo (todas são divisões com resto):
Informações importantes dadas:
-
é um inteiro positivo. - As três condições indicam os restos das divisões de
por , e . - Preciso produzir um programa em
que calcule o menor que satisfaça tudo isso.
Passo 2
Interpretando matematicamente as condições: “divisão com resto” é expressa por congruência modular. Escrevemos cada condição assim:
Explicando de forma didática: a congruência
significa que, ao dividir
por
, o resto é
. Por exemplo,
quer dizer que
deixa resto
ao dividir por
.
Passo 3
Estratégia para resolver: podemos usar dois caminhos:
- método direto/bruto (programático): testar
e verificar as três congruências até achar o menor que satisfaça todas; - método teórico (Sistema de congruências / Teorema Chinês dos Restos): resolver analiticamente as congruências para encontrar a solução mínima de forma fechada.
Para o programa emé mais simples e robusto usar a abordagem de teste sequencial (brute force). Antes de escrever o programa, vou mostrar a solução teórica (útil para entender o que o programa vai encontrar) e checar o resultado.
Passo 4
Começo resolvendo duas congruências por vez, de forma elementar (sem formalizar o Teorema Chinês): da primeira temos que existe
tal que
Substituo isso na segunda congruência
:
Subtraindo
dos dois lados:
Passo 5
Para resolver
preciso do inverso de
módulo
. Explico de forma simples: o inverso de
módulo
é um número
entre
e
tal que
. Testando mentalmente:
Logo o inverso de
módulo
é
. Multiplicando ambos os lados da congruência por
obtemos
Isto significa que existe
tal que
. Substituindo em
dá:
Portanto já reduzimos o sistema para uma única congruência:
Passo 6
Agora imposto a terceira congruência
usando
:
Subtraindo
dos dois lados:
É mais prático reduzir
módulo
:
(pois
). Assim a congruência fica
E
. Logo
Passo 7
Da última congruência para
temos que existe
tal que
. Substituindo na expressão de
:
Isto mostra que todas as soluções são da forma
Como queremos o menor inteiro positivo, tomamos
, obtendo
Passo 8
Verificação dos restos com
(contando passo a passo para você poder reproduzir na prova sem calculadora):
- Dividindo por
: , resto . Portanto . - Dividindo por
: , resto . Portanto . - Dividindo por
: , resto . Portanto .
Tudo confere:é realmente a menor solução positiva. (Observação: o módulo combinado é , por isso as soluções repetem a cada unidades.)
Passo 9
Agora o programa em
. Para ser simples, seguro e fácil de entender (ideal na prova/programação rápida), uso a estratégia de busca incremental: começo em
e incremento até encontrar o primeiro
que satisfaça as três condições com o operador resto .
%. Esse método é direto e curto; para estes módulos pequenos é instantâneo. Abaixo está o código em
Resposta
#include <stdio.h>
int main(void) {
int n = 1;
while (1) {
if (n % 3 == 2 && n % 5 == 3 && n % 7 == 4) {
printf("%d\n", n);
break;
}
n++;
}
return 0;
}