Cześć, mam problem z zadaniem.
Niech n będzie pewną liczba naturalną. Ile reszt modulo n jest względnie pierwszych z liczbą 30? Obliczenia przeprowadź dla n=1000.
Bardzo proszę o pomoc bo kompletnie nie wiem jak się wziąć za to zadanie.
Z góry dzięki za pomoc.
Ile reszt modulo
- 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 reszt modulo
\(\displaystyle{ 30=3\cdot 2\cdot 5}\), więc należy policzyć liczby spośród \(\displaystyle{ 0,1,2\ldots 999}\), które nie dzielą się przez \(\displaystyle{ 2}\), przez \(\displaystyle{ 3}\) lub przez \(\displaystyle{ 5}\).
Można to zrobić z użyciem zasady włączeń i wyłączeń. Znasz ją?
Można to zrobić z użyciem zasady włączeń i wyłączeń. Znasz ją?
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Re: Ile reszt modulo
\(\displaystyle{ 30 = 3 \cdot 2 \cdot 5}\)
Ogólnie to można to zrobić ze znanej zależności, że liczb podzielnych przez \(\displaystyle{ k}\) w zbiorze \(\displaystyle{ N = \left\{0, 1, 2, ..., n-1}\right\}}\) jest \(\displaystyle{ \lfloor {\frac{n-1} {k}} \rfloor + 1}\)
Rozwiązanie (Nie patrz, dopóki nie rozwiążesz )
Ogólnie to można to zrobić ze znanej zależności, że liczb podzielnych przez \(\displaystyle{ k}\) w zbiorze \(\displaystyle{ N = \left\{0, 1, 2, ..., n-1}\right\}}\) jest \(\displaystyle{ \lfloor {\frac{n-1} {k}} \rfloor + 1}\)
Rozwiązanie (Nie patrz, dopóki nie rozwiążesz )
Ukryta treść: