(Baltic Way 2018) Нека је p непаран прост број. Одредити све природне бројеве n за које је \sqrt{n^2-np} природан број.
Нека је n природан број такав да је \sqrt{n^2-np}=\sqrt{n(n-p)} природан број.
Ако n није потпун квадрат, онда постоји бар један његов прост делилац q који у n учествује непаран број пута као прост чинилац. Како је \sqrt{n(n-p)} природан број, тј. n\cdot(n-p) потпун квадрат, то прост број q мора учествовати непаран број пута као чинилац броја n-p ( да би у n\cdot(n-p) учествовао паран број пута ). Дакле, q|(n-p) , па како q|n , то q|p , из чега следи q=p ( q и p су прости ). Овим смо добили да је p једини прост делилац броја n који у њему учествује непаран број пута као прост чинилац, а самим тим да је количник бројева n и p ( у ознаци k ) потпун квадрат. Сада добијамо да је \sqrt{n(n-p)}=\sqrt{kp(kp-p)}=\sqrt{kp^2(k-1)}=p\sqrt{k}\sqrt{k-1} природан број, из чега следи да је \sqrt{k-1} природан број, тј. да је k-1 потпун квадрат, а што није могуће јер је k потпун квадрат ( јасно је да не постоје два потпуна квадратa који се разликују за 1 ). Контрадикција.
Овим смо доказали да је n потпун квадрат. Означимо његов корен са l (n=l^2). Kako je \sqrt{n(n-p)}=l\sqrt{n-p} природан број, то је и \sqrt{n-p} природан број, означимо га са m. Сада имамо l^2-p=m^2, а одатле и p=l^2-m^2=(l-m)(l+m), па је l-m=1 и l+m=p. Из последње две једнакости добија се p=2l-1 тј. l=\frac{p+1}{2}, па је n=(\frac{p+1}{2})^2.
На основу до сада изложеног једино можемо закључути да природни бројеви различити од (\frac{p+1}{2})^2 не испуњавају услов задатка, али не и да број (\frac{p+1}{2})^2 задовољава тај услов.
Како је p непаран природан број, то је \frac{p+1}{2} природан број, па је то и (\frac{p+1}{2})^2. Сада треба проверити да ли је \sqrt{((\frac{p+1}{2})^2)^2-(\frac{p+1}{2})^2\cdot p} природан број. Ради једноставнијег рачуна, означимо природан број \frac{p+1}{2} са a. Тада је p=2a-1, па имамо \begin{aligned}\sqrt{\Big(\Big(\frac{p+1}{2}\Big)^2\Big)^2-\Big(\frac{p+1}{2}\Big)^2\cdot p}&=\sqrt{\big(a^2\big)^2-a^2\cdot(2a-1)}\\&=\sqrt{a^2(a^2-2a+1)}\\&=a\sqrt{(a-1)^2}=a(a-1).\end{aligned}Како је a(a-1) природан број (a-1 је природан број јер из p\gt 2 следи a\gt 1), то природан број (\frac{p+1}{2})^2 задовољава услов задатка.
Дакле, (\frac{p+1}{2})^2 је једини природан број са траженим особинама.
deljivost potpun kvadrat prosti brojevi