Escreva um programa em C que encontre o menor inteiro positivo \boldsymbol{n} que atenda as seguintes condições :
\mathrm{n} / 3=\mathrm{x} inteiro e resto 2
\mathrm{n} / 5=\mathrm{y} inteiro e resto 3
\mathrm{n} / 7=\mathrm{z} inteiro e resto 4

Passo 1

O enunciado pede: escrever um programa em C que encontre o menor inteiro positivo n que satisfaça simultaneamente as três condições abaixo (todas são divisões com resto):
n/3 = x\\ \text{inteiro e resto}\\\ 2
n/5 = y\\ \text{inteiro e resto}\\\ 3
n/7 = z\\ \text{inteiro e resto}\\\ 4
Informações importantes dadas:
  • n é um inteiro positivo.
  • As três condições indicam os restos das divisões de n por 3, 5 e 7.
  • Preciso produzir um programa em C que calcule o menor n 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:
n \equiv 2 \pmod{3}
n \equiv 3 \pmod{5}
n \equiv 4 \pmod{7}
Explicando de forma didática: a congruência n \equiv r \pmod{m} significa que, ao dividir n por m, o resto é r. Por exemplo, n \equiv 2 \pmod{3} quer dizer que n deixa resto 2 ao dividir por 3.

Passo 3

Estratégia para resolver: podemos usar dois caminhos:
  • método direto/bruto (programático): testar n=1,2,3,\dots e verificar as três congruências até achar o menor n 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 C é 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 a tal que
n = 3a + 2.
Substituo isso na segunda congruência n \equiv 3 \pmod{5}:
3a + 2 \equiv 3 \pmod{5}.
Subtraindo 2 dos dois lados:
3a \equiv 1 \pmod{5}.

Passo 5

Para resolver 3a \equiv 1 \pmod{5} preciso do inverso de 3 módulo 5. Explico de forma simples: o inverso de 3 módulo 5 é um número b entre 1 e 4 tal que 3b \equiv 1 \pmod{5}. Testando mentalmente:
3\cdot1 = 3 \equiv 3,\quad 3\cdot2 = 6 \equiv 1 \pmod{5}.
Logo o inverso de 3 módulo 5 é 2. Multiplicando ambos os lados da congruência por 2 obtemos
a \equiv 2 \pmod{5}.
Isto significa que existe k tal que a = 5k + 2. Substituindo em n = 3a + 2 dá:
n = 3(5k+2) + 2 = 15k + 8.
Portanto já reduzimos o sistema para uma única congruência:
n \equiv 8 \pmod{15}.

Passo 6

Agora imposto a terceira congruência n \equiv 4 \pmod{7} usando n = 15k + 8:
15k + 8 \equiv 4 \pmod{7}.
Subtraindo 8 dos dois lados:
15k \equiv -4 \pmod{7}.
É mais prático reduzir 15 módulo 7: 15 \equiv 1 \pmod{7} (pois 15 = 14 + 1). Assim a congruência fica
k \equiv -4 \pmod{7}.
E -4 \equiv 3 \pmod{7}. Logo
k \equiv 3 \pmod{7}.

Passo 7

Da última congruência para k temos que existe t tal que k = 7t + 3. Substituindo na expressão de n:
n = 15k + 8 = 15(7t + 3) + 8 = 105t + 45 + 8 = 105t + 53.
Isto mostra que todas as soluções são da forma
n = 105t + 53,\quad t \in \mathbb{Z}.
Como queremos o menor inteiro positivo, tomamos t = 0, obtendo
n = 53.

Passo 8

Verificação dos restos com n=53 (contando passo a passo para você poder reproduzir na prova sem calculadora):
  • Dividindo por 3: 53 = 3\cdot17 + 2, resto 2. Portanto 53 \equiv 2 \pmod{3}.
  • Dividindo por 5: 53 = 5\cdot10 + 3, resto 3. Portanto 53 \equiv 3 \pmod{5}.
  • Dividindo por 7: 53 = 7\cdot7 + 4, resto 4. Portanto 53 \equiv 4 \pmod{7}.
    Tudo confere: 53 é realmente a menor solução positiva. (Observação: o módulo combinado é \mathrm{lcm}(3,5,7)=105, por isso as soluções repetem a cada 105 unidades.)

Passo 9

Agora o programa em C. 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 n=1 e incremento até encontrar o primeiro n 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 C.

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;
}

Exercícios relacionados