Question

Seja A um número inteiro positivo que é múltiplo de 5 e tal que  a+1 é múltiplo de 7,  a+2 é múltiplo de 911 e a+3 é múltiplo de 11. Determine o menor valor possível de a.

Answer 1

Vemos que o primeiro numero que satisfaz a primeira condicao eh 0, porem 0 nao satisfaz a segunda condicao. O primeiro numero que satisfaz as duas primeiras condicoes eh 20, porem este nao satisfaz a terceira condicao. Numeros que satisfazem a primeira e segunda condicao vao se repetir a cada 35 numeros (5×7). Andando nesse intervalo vemos que o primeiro numero a satisfazer as 3 primeiras condicoes eh 160, mas este nao satisfaz a ultima condicao, entao agora andamos num intervalo de 315 (no caso 5×7×9). Andando neste intervalo vemos que o primeiro numero a satisfazer todas as condicoes eh: 1735

Answer 2

Pelo enunciado $a$ é divisível por $5$, então $a=5m~~(i)$, com $m\in\mathbb{N}$

Além disso, $a+1$ é múltiplo de $7$. Desse modo, $a+1=7n$, ou seja, $a=7n-1~~(ii)$

Igualando $(i)$ e $(ii)$:

$5m=7n-1~\longrightarrow~7n-5m=1$

Uma solução particular é $(n_0,m_0)=(-2,-3)$, pois $7\cdot(-2)-5\cdot(-3)=1$

As soluções gerais são da forma:

$n=-2-5t$
$m=-3-7t$, sendo $t$ um inteiro

Substituindo em $(i)$:

$a=5m~\longrightarrow~a=5\cdot(-3-7t)~\longrightarrow~a=-15-35t~~(iii)$

Como $a+2$ é múltiplo de $9$, temos que $a+2=9k$, isto é, $a=9k-2~(iv)$, com $k\in\mathbb{N}$

Analogamente, $a+3$ é múltiplo de $11$. Assim, $a+3=11q$ e então $a=11q-3~~(v)$

Igualando $(iv)$ e $(v)$:

$9k-2=11q-3~\longrightarrow~11q-9k=1$

Note que $11\cdot5-9\cdot6=1$. Desse modo, $(q_0,k_0)=(5,6)$ é uma solução particular

As soluções gerais são da forma:

$q=5-9p$
$k=6-11p$, sendo $p$ um inteiro

Substituindo em $(iv)$:

$a=9k-2~\longrightarrow~a=9\cdot(6-11p)-2~\longrightarrow~a=52-99p~~(vi)$

Igualando $(iii)$ e $(vi)$:

$-15-35t=52-99p~\longrightarrow~99p-35t=67$

Agora a solução particular não é trivial. Vamos utilizar o Algoritmo do mdc de Euclides e a relação de Bézout.

O Lema de Euclides: Dados inteiros $a$ e $b$, os divisores comuns de $a$ e $b$ são os mesmos que os divisores comuns de $a$ e $b-c\times a$, para todo número inteiro $c$ fixado.

Isto é, $\text{mdc}(a,b)=\text{mdc}(a,b-c\times a)$

Relação de Bézout: dados inteiros $a$ e $b$, quaisquer, mas não ambos nulos, existem dois inteiros $x$ e $y$ tais que $\text{mdc}(a,b)=ax+by$

Sendo $a=99$ e $b=35$, temos:

$\text{mdc}(99,35)=\text{mdc}(35,99-35\times2)=\text{mdc}(35,29)\\\text{mdc}(99,35)=\text{mdc}(29,35-29)=\text{mdc}(29,6)\\\text{mdc}(99,35)=\text{mdc}(6,29-6\times4)=\text{mdc}(6,5)\\\text{mdc}(99,35)=\text{mdc}(5,6-5)=\text{mdc}(5,1)=1$

Observe:

$6-5=1$

Mas:

$6=35-29\\6=35-(99-35\times2)\\6=35-99+35\times2\\6=35\times3-99$

$5=29-6\times4$

Como $29=99-35\times2$  e $6=35\times3-99$ então:

$5=99-35\times2-(35\times3-99)\times4\\5=99-35\times2-35\times3\times4+99\times4\\5=99+99\times4-35\times2-35\times12\\5=99\times5-35\times14$

Substituindo em $6-5=1$:

$6-5=1\\35\times3-99-(99\times5-35\times14)=1\\35\times3-99-99\times5+35\times14=1\\35\times17-99\times6=1$

Multiplicando os dois lados dessa igualdade por $67$:

$35\times17\times67-99\times6\times67=1\times67$
$35\times1139-99\times402=67$

Ou seja, $99\times(-402)-35\times(-1139)=67$

Desse modo, $(p_0,t_0)=(-402,-1139)$ é uma solução particular.

As soluções gerais são da forma:

$p=-402-35z$
$t=-1139-99z$, sendo $z$ um inteiro.

Substituindo em $(vi)$:

$a=52-99p~\longrightarrow~a=52-99\cdot(-402-35z)$

$a=52+39798+3465z~\longrightarrow~a=39850+3465z$

Queremos o menor valor possível de $a$, lembrando que $a>0$

Note que:

$a>0~\longrightarrow~39850+3465z>0~\longrightarrow~3465z>-39850$

ou seja, $z>\dfrac{-39850}{3465}~\longrightarrow~z>-11,5$

Logo, o menor valor positivo de $a$ é obtido quando $z=-11$

Para $z=-11$:

$a=39850+3465\cdot(-11)~\longrightarrow~a=39850-38115~\longrightarrow~a=1735$

Portanto, a resposta é $1735$