3360446545

Materiały dydaktyczne - Matematyka Dyskretna (Zestaw 2)

Rozwiązania.

3. Niech a = p“^lp₂² • • • p^^k, gdzie p\ < P2 < • • Pk są liczbami pierwszymi i a* > 0 są liczbami naturalnymi. Jeśli teraz b jest dzielnikiem a, to b = jĄ'p%² ■ • gdzie 0 ^ 0i < aj i odwrotnie, każda liczba tej postaci z podanymi ograniczeniami na /3{ jest dzielnikiem a. Stąd, liczba dzielników liczby a jest równa

(<*i + l)(ct₂ + !)••• (a*, + 1).

W szczególności wynika z tego, że jeśli liczba dzielników liczby a jest liczbą pierwszą, to a jest potęgą liczby pierwszej. Zatem najmniejszą liczbą która ma 2, 3, 5, 7 dzielników są odpowiednio 2, 2² = 4, 2⁴ = 16, 2⁶ = 64. Wyznaczenie pozostałych najmniejszych liczb mających dokładnie k dzielników z k ^ 10 pozostawiam czytelnikowi.

5. Zauważmy na początek, że

66 = 81-27 + 9 + 3 77 = 81-3-1 88 = 81 + 9-3 + 1

Czyli wskazane liczby są sumami potęg trójki poprzedzonych znakiem plus lub minus. Pokażemy indukcyjnie, że jeżeli liczba naturalna a jest mniejsza od

ofc+l _ 1

1 + 3 + 3² + 3³ H-----1- 3^fc =---,    (1)

to można ją przedstawić w postaci ao +    • 3 + a2 • 3² + • • • + a& • 3^fc, gdzie aj € {—1, 0, 1}.

Dowód tego stwierdzenia dla małych wartości k pozostawiam do samodzielnego przeprowadzenia. Załóżmy że jest ono prawdziwe dla wszystkich k < n i dowodzimy, że jeśli

3ⁿ+i _ i

a < 1 + 3 + 3² + 3³ +----f- 3" =---

, to

a = ao + ai ■ 3 + d2 • 3² + • • • + d_n • 3ⁿ

gdzie dj G {—1, 0, 1}. Przedział

o,

3"⁺¹ - 11

podzielmy na trzy części: [0,    , (³'‘₂~¹,3”], ^3", —-j. Pierwsze dwa mają po ^y^ +1 liczb

całkowitych, a ostatni o jedną mniej. Rzeczywiście, dla pierwszego z nich jest to oczywiste, dla drugiego mamy

3ⁿ -

3" - 1    2 • 3" - 3ⁿ + 1

a dla trzeciego

2

₃n+i _ _l

3ⁿ + 1 2

3"

3 • 3ⁿ — 2 • 3” — 1    3” - 1

2 2 2

Niech teraz a będzie dowolną liczbą całkowitą z przedziału |o, ³'^>+2‘~¹ j. Jeżeli a G [0, ³'‘₂~¹], to oczywiście, na mocy założenia idukcyjnego można ją przedstawić w żądanej postaci. Jeśli a G (^y^,3ⁿ], tzn.

3" — 1

< d < 3”,

to 3ⁿ — d < 3ⁿ — ³ ₂ ¹ = ³    , a zatem ponownie na mocy założenia indukcyjnego

3” — d = do + Oi • 3 + d2 • 3² H-----1- dra_i3" ^x, gdzie dj G {—1,0,1}

2