Divisibilidade

Encontre o menor inteiro que, dividido por 29 deixa resto 5, e dividido por 31 dá resto 28.

igormf escreveu:Encontre o menor inteiro que, dividido por 29 deixa resto 5, e dividido por 31 dá resto 28.

Boa tarde, Igor.

N = o número a ser procurado
p = o quociente inteiro de N/29
q = o quociente inteiro de N/31

29.p+ 5 = 31.q + 28 ...... (I)
29.p - 31.q = 28 - 5

29.p - 31.q = 23 → Equação Diofantina (2 incógnitas, 1 equação, incógnitas ineiras)

p = (31.q + 23)/29 → separamos os quocientes inteiros dos fracionarios:
p = q + (2q + 23)/29

Como p e q devem ser inteiros, a fração também deverá sê-lo; portanto, faremos:

(2q + 23)/29 = m
2q + 23 = 29m
2q = 29m - 23
q = (29m - 23)/2 → novamente separamos os quocientes inteiros dos fracionários:
q = 14m - 11 + (m - 1)/2

Como q e m devem ser inteiros, a fração igualmente deverá sê-lo; portanto, faremos:

(m - 1)/2 = n
m - 1 = 2n
m = 2n + 1 → aplicamos este valor de m na fórmula sublinhada de q:

q = [29(2n+1) - 23]/2 = (58n + 29 - 23)/2 = (58n + 6)/2
q = 29n + 3

A seguir, aplicamos o valor supra de q à formula grifada de p:

p = [31.(29n + 3) + 23]/29 = (899.n + 93 + 23)/29 = (899.n + 116)/29
p = 31n + 4

Ora, p e q, além de inteiros, deverão ser posiivos; logo, faremos:
q → 29n+3 > 0 → 29n > -3 → n > -3/29 → n ≥ 0
p → 31n+4 > 0 → 31n > -4 → n > -4/31 → n ≥ 0

Aplicando-se, portanto, o menor valor de n (=0) às fórmulas de p e q, obtemos:
p = 31n + 4 = 31.0 + 4 = 4
q = 29n + 3 = 29.0 + 3 = 3

Substituindo, na fórmula (I), p e q respectivamente por 4 e 3, fica:
29.p + 5 = 31.q + 28
29.4 + 5 = 31.3 + 28
116 + 5 = 93 + 28
121 = 121





Um abraço.

por congruência linear :

vou fazer pelo teorema do resto chinês:



vamos substituir (I) na segunda congruência:



substituindo (II) em (I) :



c=0,já que pede o menor inteiro positivo.:pirat:

Man Utd escreveu:por congruência linear :

vou fazer pelo teorema do resto chinês:



vamos substituir (I) na segunda congruência:



substituindo (II) em (I) :



c=0,já que pede o menor inteiro positivo.:pirat:

Não entendi a parte em que você conclui que  e por que multiplicar por 15?
Obrigado.

igormf escreveu:Não entendi a parte em que você conclui que  e por que multiplicar por 15?
Obrigado.

bem temos o seguinte:



repare que o nosso objetivo é isolar o "b" justamente para susbstituímos na outra equação,então se multiplicarmos por 15 os dois lados ,iremos conseguir isolar o "b":



ora, 435≡1 mod (31) e 345≡4 mod(31) então chegamos em:




que é o queremos,já que assim poderemos susbtituir na outra equação.:pirat:

Minha solução poderia ser aceita?
n=29*a+5  (equação x) 
n=31*b+28 (equação y)
x-y=
0=29a-31b-23
29a=31b+23
a=(31b+23)/29(equaçao z)
Como a e b são naturais,a equação z,também deve resultar em um número inteiro positivo*
(0logo se b=1 z não é inteiro
b=2 z também não é inteiro
e se b=3 z é inteiro
substituindo:
n=31*3+28=121
Logo a resposta é (121)

John von Neumann jr escreveu:Minha solução poderia ser aceita?
n=29*a+5  (equação x) 
n=31*b+28 (equação y)
x-y=
0=29a-31b-23
29a=31b+23
a=(31b+23)/29(equaçao z)
Como a e b são naturais,a equação z,também deve resultar em um número inteiro positivo*
(0logo se b=1 z não é inteiro
b=2 z também não é inteiro
e se b=3 z é inteiro
substituindo:
n=31*3+28=121
Logo a resposta é (121)

Bom dia e Feliz Natal, John! 
Sim, com certeza, parabéns!