Question

Fie n si k, prime intre ele. Aratati ca primii n multipli nenuli ai lui k dau resturi diferite prin impartirea la n

Answer 1

$Primii~n~multipli~nenuli~ai~lui~k~sunt:~k,~2k,~3k,...,nk. \\ \\ Presupunem~prin~reducere~la~absurd~ca~exista~p,q \in \{1,2,...,n \}~cu \\ \\ p > q~astfel~incat~pk~si~qk~sa~dea~acelasi~rest~la~impartirea~prin~n. \\ \\ Daca~pk~si~qk~dau~acelasi~rest~la~impartirea~prin~n,~atunci~ \\ \\ diferenta~lor~este~divizibila~cu~n~(demonstratia~este~triviala~si~ \\ \\ provine~din~teorema~impartirii~cu~rest;~am~adaugat~la~sfarsit \\ \\ demonstratia) .$

$Deci~pk-qk=k(p-q)~~ \vdots~n. \\ \\ Insa~(k,n)=1,~si~atunci~p-q~este~multiplu~nenul~al~lui~n.~Insa \\ \\ 1 \leq p-q \leq n-1 \Rightarrow~p-q~nu~poate~fi~multiplu~a~lui~n. \\ \\ Deci~am~obtinut~o~contradictie.~Prin~urmare,~presupunerea~facuta \\ \\ este~falsa,~si~astfel~solutia~se~incheie.$

$Acum~demonstratia~promisa:~Sa~zicem~ca~x~si~y~sunt~numere \\ \\ naturale~care~dau~acelasi~rest~la~impartirea~prin~n~(n \in N). \\ \\ Atunci~avem:~x=nc_1+r~si~y=nc_2+r~(restul~fiind~r,~iar~c_1~si \\ \\ c_2~caturile~obtinute~prin~impartirea~la~n). \\ \\ Atunci~x-y=nc_1-nc_2=n(c_1-c_2)~ \vdots ~n.$