Question

(Aritmetica: Critério de divisibilidade por 47)

Seja $n=10a+b$ um número natural, com a, b ∈ ℕ.

a) Mostre que se $a-14b\equiv r~~\mathrm{(mod~}47),$ então $10a+b\equiv 10r~~\mathrm{(mod~}47).$

b) A alínea anterior fornece um algoritmo para calcular o resto da divisão de qualquer número natural por 47. Utilizando este algoritmo, calcule resto da divisão de 15334 por 47.​

Answer 1

a)

$a - 14b \equiv r \pmod {47}\\10(a-14b)\equiv 10r \pmod{47}\\10a - 140b \equiv 10r \pmod{47}\\10a \equiv 10r + 140b \pmod{47}\\10a + b \equiv 10r + 141b \pmod{47}\\10a + b \equiv 10r + 47(3b) \pmod{47}\\10a + b\equiv 10r\pmod{47}$

b) $15334$ no formato $10a + b$:

$15334 = 10 \cdot 1533 + 4$

Ou seja, em formato $a - 14b$:

$1533 - 14 \cdot 4 = 1477$

Portanto 1477 tem resto 10 vezes menor que 15334.

Agora, 1477 também pode ser escrito como $10a + b$:

$1477 = 10\cdot 147 + 7$

Consequentemente:

$147 - 14 \cdot 7 = 49$ (que evidentemente deixa resto 2).

Então 49 tem resto 10 vezes menor que 1477.

Logo, o resto de 1477 é $10 \cdot 2 = 20$, e o resto de 15334 é $10 \cdot 20 = 200$. Este número ainda pode ser simplificado:

$200 \equiv 12 + 188 \pmod {47}\\200 \equiv 12 + 47 \cdot 4 \pmod {47}\\200 \equiv 12 \pmod {47}$

Portanto:

$15334 \equiv 12 \pmod {47}$