Oto treść zadania:
Ile jest naturalnych liczb trzycyfrowych względnie pierwszych z liczbą \(\displaystyle{ 60}\)?
Wiem, że liczby względnie pierwsze to takie, których \(\displaystyle{ NWD = 1}\), czyli dla 60 będzie to np. 101, natomiast nie wiem za bardzo jak policzyć wszystkie takie liczby, ponieważ nie znalazłam żadnej zależności.
Ile jest liczb względnie pierwszych z daną liczbą
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Ile jest liczb względnie pierwszych z daną liczbą
Mamy \(\displaystyle{ 60=2^{2}\cdot 3^{1}\cdot 5^{1}}\), więc wystarczy, że zliczysz liczby trzycyfrowe, które nie są podzielne przez \(\displaystyle{ 2,3}\) ani \(\displaystyle{ 5}\). Można to zrobić korzystając z zasady włączeń i wyłączeń.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Ile jest liczb względnie pierwszych z daną liczbą
Zgadza się.lola456 pisze: A gdyby było np. 75 to zliczam liczby trzycyfrowe które nie są podzielne przez 5 ani 3?
To może zacznę, żeby pokazać, jak mniej więcej się to robi:
wśród liczb \(\displaystyle{ 1,2\ldots n}\) mamy \(\displaystyle{ \left\lfloor \frac{n}{k}\right\rfloor}\) liczb podzielnych przez \(\displaystyle{ k\in \NN^{+}}\).
A zatem wśród liczb \(\displaystyle{ 1,2 \ldots 999}\) mamy \(\displaystyle{ \left\lfloor \frac{999}{3}\right\rfloor=333}\) liczby podzielne przez \(\displaystyle{ 3}\), natomiast wśród liczb \(\displaystyle{ 1,2\ldots 99}\) odnajdziemy ich \(\displaystyle{ \left\lfloor \frac{99}{3}\right\rfloor=33}\). Czyli jest \(\displaystyle{ 333-33=300}\) liczb trzycyfrowych podzielnych przez \(\displaystyle{ 3}\).
W ten sposób (zasadę włączeń i wyłączeń masz tutaj: możesz wyliczyć, ile liczb naturalnych trzycyfrowych dzieli się przez co najmniej jedną z liczb \(\displaystyle{ 2,3,5}\), a potem uzyskasz wynik, odejmując od liczby wszystkich liczb naturalnych trzycyfrowych liczbę tych, które dzielą się przez co najmniej jedną spośród \(\displaystyle{ 2,3,5}\).