Re: Problema de inteiros

[Augusto Morgado <morgado@xxxxxxxxxxxxxxx>]

> Edmilson escreveu:
> 
> Caros amigos da lista,
> 
> Uma equação diofantina  a.x + b.y = c, em que a diferente de zero ou b
> diferente de zero, admite solução se, e somente se,
> d = mdc (a,b) divide c.
> 
> No caso particular de mdc (a, b) =1, toda equação diofantina da forma
> acima admite infinitas soluções inteiras, pois, 1 | a, para todo a
> inteiro.
> 
> No caso em que mdc (a,b) = d, por definição  d | a   e   d | b , sendo
> (m,n) uma solução da equação diofantina, temos :
> am+bn = c, e portanto d |am + bn, ou seja, d | c.
> Por outro lado, se d = mdc (a,b), um teorema, já comentado pelo Prof.
> José Paulo, garante que existem inteiros m e n tais que
> a.m + b.n = d como d | c (hipótese), esiste k inteiro, tal que c =
> d.t, para algum t inteiro.
> Asssim, c = d.t = (a.m+b.n).t = a(mt)+b.(n.t). Logo, (m.t, n.t ) é a
> ssoluçào da equação a.x+b.y = c.
> 
> Atenciosamente,
> Edmilson
> http://www.abeunet.com.br/~edmilson
> edmilson@abeunet.com.br
> -----Mensagem Original-----
> De: Ecass Dodebel <ecassdodebel@hotmail.com>
> Para: <obm-l@mat.puc-rio.br>
> Enviada em: Segunda-feira, 24 de Abril de 2000 20:55
> Assunto: Re: Problema de inteiros
> 
> >
> > Caro Marcos Eike Tinen dos Santos,
> >
> > concordo com a sua colocação de que importante é entender que quando
> 
> > mdc(x,y)>1 não podemos obter todos os números somando multiplos
> desses.
> > Agora, tratemos do outro problema onde eu me compliquei todo:
> > queremos que ax + by = n, com mdc(x,y)=1 e a,b > 0, para isso temos
> que
> > descobrir um N onde satisfazemos essas condições com o n > N.
> >
> > Na minha solução acho que para N = 2xy sempre conseguimos, mas usei
> aquele
> > processo que eu achei meio artificial e confuso de somar e diminuir
> axy...
> > alguma outra idéia?
> >
> > Obrigado!
> >
> >
> > >From: "Marcos Eike Tinen dos Santos" <mjsanto@carajasnet.com.br>
> > >Reply-To: obm-l@mat.puc-rio.br
> > >To: <obm-l@mat.puc-rio.br>
> > >Subject: Re: Problema de inteiros
> > >Date: Mon, 24 Apr 2000 19:31:30 -0300
> > >
> > >sim, amigo José, eu só comentei, pois acredito que este seja um dos
> pontos
> > >cruciais na solução do problema.
> > >
> > >
> > >Ats,
> > >Marcos Eike
> > >
> > >----- Original Message -----
> > >From: José Paulo Carneiro <jpcarneiro@openlink.com.br>
> > >To: <obm-l@mat.puc-rio.br>
> > >Sent: Segunda-feira, 24 de Abril de 2000 17:51
> > >Subject: Re: Problema de inteiros
> > >
> > >
> > > > Se nao forem primos entre si, eh falso. Como voce vai obter 5,
> que eh
> > >impar,
> > > > como uma soma de multiplos de 4 e 6?
> > > >
> > > > -----Mensagem original-----
> > > > De: Marcos Eike Tinen dos Santos <mjsanto@carajasnet.com.br>
> > > > Para: obm-l@mat.puc-rio.br <obm-l@mat.puc-rio.br>
> > > > Data: Segunda-feira, 24 de Abril de 2000 11:06
> > > > Assunto: Re: Problema de inteiros
> > > >
> > > >
> > > > >Um dos fatos importantes a ser considerado, é: Por que o
> problema nos
> > >impõe
> > > > >a propriedade de que eles devem ser primos entre si. Será que
> foi por
> > > > acaso?
> > > > >Eu penso que essa resposta é a metade do caminho para uma
> solução bem
> > > > >formulada.
> > > > >
> > > > >Ats,
> > > > >Marcos Eike
> > > > >
> > > > >
> > > > >----- Original Message -----
> > > > >From: Ecass Dodebel <ecassdodebel@hotmail.com>
> > > > >To: <obm-l@mat.puc-rio.br>
> > > > >Sent: Sábado, 22 de Abril de 2000 17:42
> > > > >Subject: Problema de inteiros
> > > > >
> > > > >
> > > > >> E ai, pessoal?
> > > > >>
> > > > >> Eu estava tentando resolver um dos problemas propostos na
> última
> > >Eureka!
> > > > e
> > > > >> acabei chegando em uma parte que consigo seguir adiante mas é
> muito
> > > > >> trabalhosa a minha prova, e não sei se está bem certa. Lá
> vai.
> > > > >>
> > > > >> 1) Sejam x e y dois números primos entre si. Provar que
> podemos obter
> > > > >> qualquer número somando múltiplos de x e de y.
> > > > >>
> > > > >> Solução.
> > > > >> Queremos provar que para todo o x,y,n dados, podemos achar f
> e g de
> > >modo
> > > > >que
> > > > >>
> > > > >> fx + gy = n  ( a soma de múltiplos de x e de y dão o n )
> > > > >>
> > > > >> Isola-se o f, ou o g... no caso isolei o f:
> > > > >>
> > > > >> f = (n - gy)/x
> > > > >>
> > > > >> Agora nos basta encontrar g de modo que x | n - gy. Para quem
> sabe um
> > > > >> pouquinho de Teoria dos Números, eu acho que se variarmos o y
> num
> > >s.c.r.
> > > > >> então o n - gy será um s.c.r. módulo x, e estaria provado.
> Mas vamos
> > >por
> > > > >> partes:
> > > > >>
> > > > >> Suponhamos que
> > > > >>
> > > > >> n - g1y =/= n - g2y (mod x)    '=/= incongruente
> > > > >> g1y =/= g2y (mod x)  ==> afirmação similar a x não divide
> y(g1-g2)
> > > > >>
> > > > >> Como  mdc(x,y)=1 então
> > > > >>
> > > > >> g1 =/= g2 (mod x)
> > > > >>
> > > > >> Vale tambem que se g1 =/= g2 (mod x) então n - g1y =/= n -
> g2y (mod
> > >x).
> > > > >> Agora escolhemos x números incongruentes módulo x
> (g1,...,gx), ou
> > >seja,
> > > > >que
> > > > >> nunca deixem o mesmo resto na divisão por x. E
> necessariamente:
> > > > >>
> > > > >> n - giy =/= n - gjy (mod x) para todo o i e j
> > > > >>
> > > > >> Ou seja, nesses x números (n-g1y,...,n-gxy), todos são
> incongruentes
> > > > >módulo
> > > > >> x, e como existem apenas x restos possíveis na divisão por x,
> > > > >> necessariamente algum deles deixará resto zero na divisão por
> x, e
> > > > >portanto
> > > > >> haverá um g, tal que:
> > > > >>
> > > > >> f = (n - gy)/x será inteiro, e está provado o enunciado.
> > > > >>
> > > > >> 2) Sejam x e y dois números primos entre si. Prove que existe
> um N,
> > >de
> > > > >modo
> > > > >> que para todo o n > N, podemos escolher múltiplos positivos
> de x e de
> > >y
> > > > >que
> > > > >> somados dão n. Nessas condições teremos que ter
> > > > >>
> > > > >> Solução.
> > > > >> O problema pede para que mostremos que existem f e g
> positivos de
> > >modo
> > > > >que,
> > > > >> para n > N
> > > > >>
> > > > >> fx + gy = n  (lembrando que é todo mundo inteiro nesse
> e-mail)
> > > > >>
> > > > >> A minha idéia é a seguinte, claramente xy - yx = 0, e
> portanto para
> > >todo
> > > > o
> > > > >a
> > > > >> vale axy - ayx = 0, daí:
> > > > >>
> > > > >> fx + gy + axy - ayx = n
> > > > >> (f + ay)x + (g - ax)y = n, para qualquer a que escolhermos
> > > > >>
> > > > >> Quero mostrar que existirá um a, a partir de um dado n, para
> que f +
> > >ay
> > >e
> > > > >g
> > > > >> - ax sejam ambos positivos.
> > > > >>
> > > > >> Conseguimos escolher a de modo que (f + ay)x - (g - ax)y = fx
> - gy +
> > >2ayx
> > > > >> esteja entre -yx e yx, basta mostrar que nesse intervalo
> teremos f+ay
> > >e
> > > > >g-ax
> > > > >> sempre positivos.
> > > > >>
> > > > >> Tanto f+ay quanto g-ax podem ficar entre [ n-xy ; n+xy ], ou
> seja
> > >basta
> > > > >que
> > > > >> n-xy>0 e portanto que n > xy. Logo para N = xy vale o
> enunciado.
> > > > >>
> > > > >>
> > > > >> Obrigado para quem leu! E tem algum erro?
> > > > >> Valeu...
> > > > >>

Caríssimos:
Pode-se provar que a equação diofantina ax+by=n com a e b positivos
primos entre si admite soluções não-negativas para todo n a partir de
ab-a-b (exclusive).Ou seja, o N citado vale ab-a-b.
Morgado