Wyznaczyć najmniejszą możliwą liczbę

[41421356]

Wyznacz najmniejszą liczbę naturalną, która jest podzielna przez liczby \(\displaystyle{ 3,4,8}\), natomiast przy dzieleniu tej liczby przez \(\displaystyle{ 5}\) otrzymujemy resztę \(\displaystyle{ 1}\).

Interesuje mnie najbardziej "matematyczne" rozwiązanie, bez liczenia tego na piechotę. Pozdrawiam.

[kerajs]

\(\displaystyle{ NWW(3,4,8)=24 \\
24 \mod 5=4}\)
Szukasz najmniejszej naturalnej k spełniającej równanie
\(\displaystyle{ 4k \mod 5=1}\)
(albo \(\displaystyle{ -k \mod 5=1}\))
więc wynikiem będzie liczba 24k (czyli 96)

Jest wystarczająco matematycznie?

[41421356]

Ok, tylko w jaki sposób szukam tej najmniejszej liczby naturalnej \(\displaystyle{ k}\)? Czy to nie jest właśnie liczenie tego na piechotę?

[Premislav]

Można nie na piechotę, ale akurat tutaj to jest chyba nawet gorsze. Wiesz, że ta liczba ma być postaci \(\displaystyle{ 24k, \ k\in\NN}\), czyli ma zachodzić
\(\displaystyle{ 24k\equiv 1\pmod{5}\\4k\equiv 1\pmod{5}}\)
Teraz znajdujesz element odwrotny do \(\displaystyle{ 4}\) modulo \(\displaystyle{ 5}\), czyli takie \(\displaystyle{ x\in \left\{1,2,3,4\right\}}\), że \(\displaystyle{ 4\cdot x\equiv 1\pmod{5}}\). To jest \(\displaystyle{ 4}\) (na upartego można to znaleźć z rozszerzonego algorytmu Euklidesa, co dobrze działa w ogólności, ale tutaj już chyba szybciej podstawić i sprawdzić), mnożymy więc tę kongruencję stronami i mamy
\(\displaystyle{ k\equiv 4\pmod{5}}\),
stąd \(\displaystyle{ k=5l+4, \ l=0,1\ldots }\)
(bo \(\displaystyle{ k}\) jest liczbą naturalną), a więc
\(\displaystyle{ 24k=24(5l+4)}\), najmniejsza będzie dla \(\displaystyle{ l=0}\), czyli \(\displaystyle{ 96}\).

[kerajs]

PS
Nie bez powodu podałem alternatywne równanie: \(\displaystyle{ -k \mod 5 =1}\) , gdyż z niego od razu (i bez liczenia) widać że \(\displaystyle{ k=4 }\) .

[41421356]

Dziękuję za wskazówki.