Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

5. Megoldási útmutató

5. Megoldási útmutató

1. x n + 1 = x 2 n - 1 x n - 1 = ? d | 2 n F d ( n ) ? d | n F d ( n ) .

2. a) Az f ( n ) = F ( n ) - ? d | n d //<// n f ( d ) rekurzió definiálja f -et.

b) M ( 1 ) = µ ( 1 ) = 1 . Ha n //>// 1 és prímosztói p 1 , …, p r , akkor

M ( n ) = ? d | n µ ( d ) = ? H ? { 1 , , r } ( - 1 ) | H | = r 0 - r 1 + ? + ( - 1 ) r r r = ( 1 - 1 ) r = 0 .

c) Egyszerűsítsük a 0 n , 1 n , …, n - 1 n törteket, amíg lehet. Ezután ? ( d ) darab d nevezőjű lesz minden d | n -re.

d) Elég látni, hogy a jobb oldal összegzési függvénye F . Valóban,

? n | N ? d | n µ ( d ) F n d = ? n | N ? d c = n µ ( d ) F ( c ) = = ? c | N F ( c ) ? d N c µ ( d ) = ? c | N F ( c ) M N c = F ( N ) .

3. a) Elég látni, hogy a jobb oldalra teljesül (1). Valóban,

? n | N ? d | n ( x n / d - 1 ) µ ( d ) = ? n | N ? d c = n ( x c - 1 ) µ ( d ) = = ? c | N ? d N c ( x c - 1 ) µ ( d ) = ? c | N ( x c - 1 ) M N c = x N - 1 .

b) F n p ( x ) = ? d | n p ( x n p / d - 1 ) µ ( d ) = ? d | n ( x n p / d - 1 ) µ ( d ) = F n ( x p ) .

c) F n p ( x ) = ? d | n p ( x n p / d - 1 ) µ ( d ) = ? d | n ( x n p / d - 1 ) µ ( d ) · ? d | n ( x n p / d p - 1 ) µ ( d p ) = F n ( x p ) F n ( x ) .

d) Indukcióval dolgozva elég látni, hogy 2 ? n , n //>// 1 esetén ? d | n F 2 d ( x ) = - ? d | n F d ( - x ) (a ( - 1 ) -es szorzót F 2 ( x ) = - F 1 ( - x ) indokolja). Valóban,

? d | n F 2 d ( x ) = ? d | 2 n F d ( x ) ? d | n F d ( x ) = x 2 n - 1 x n - 1 = x n + 1 = - ( ( - x ) n - 1 ) = - ? d | n F d ( - x ) .

e) b) miatt elég négyzetmentes n -re bizonyítani, sőt d) miatt n = p és n = p q alakúra is elég ( p , q páratlan prímek).

a) szerint F p ( x ) = ( x p - 1 ) ( x - 1 ) = x p - 1 + x p - 2 + ? + 1 . Továbbá,

F p q ( x ) = ( x p q - 1 ) ( x - 1 ) ( x p - 1 ) ( x q - 1 ) = = x p ( q - 1 ) + 1 + x p ( q - 2 ) + 1 + ? + x - x p ( q - 1 ) + x p ( q - 2 ) + ? + 1 x q - 1 .

A számláló mindkét tagjában a kitevők teljes maradékrendszert alkotnak mod q , így F p q ( x )

± x r + q k - x r x q - 1 = ± x r + q ( k - 1 ) + x r + q ( k - 2 ) + ? + x r

alakú tagok összegeként írható, q darab, páronként különböző mod q maradékot adó r -rel.

4. a) (1) miatt ? ( n ) = gr F n összegzési függvénye ? ( n ) = n . 2. c) szerint ? -é is ez, így 2. a) szerint ? = ? .

b) Azt kell belátni, hogy F n ( x ) = x ? ( x ) F n 1 x ( n ? 2 ).

Indukcióval dolgozva elég belátni, hogy

? d | n F d ( x ) = - ? d | n x ? ( d ) F d 1 x

(a ( - 1 ) -es szorzót F 1 ( x ) = - x ? ( 1 ) F 1 1 x indokolja). Valóban, (1) és 2. c) szerint

- ? d | n x ? ( d ) F d 1 x = - x n 1 x n - 1 = x n - 1 = ? d | n F d ( x ) .

c) Nyilvánvaló.

d) Legyen F n -ben x együtthatója - ? ( n ) , ha n ? 2 , és legyen ? ( 1 ) = 1 . (1)-ben mindkét oldalon véve x együtthatóját

0 = ? d | n ? ( d ) , ha n ? 2 .

Tehát ? összegzési függvénye M , így 2. a) és 2. b) szerint ? = µ .

e) Első megoldás: Indukcióval bizonyítunk. Felhasználva 3. b)-t és d)-t feltehető, hogy n páratlan négyzetmentes. Jelölje f ( n ) x 2 együtthatóját F n -ben. Belátjuk, hogy ha n páratlan négyzetmentes és k darab prím szorzata, akkor

f ( n ) = ( - 1 ) k + 1 + 1 2 = 1 - µ ( n ) 2 .

Ezt az állítást k szerinti indukcióval bizonyítjuk. Ha k = 1 , akkor F n ( x ) = 1 + x + x 2 + + x n - 1 , tehát f ( n ) = 1 és így az állítás igaz. Legyen k //>// 1 és n = m p . Ekkor 3. c) szerint F n ( x ) · F m ( x ) = F m ( x p ) , tehát az indukciós feltevés és 4. d) alapján

1 + ( - 1 ) k + 1 x + f ( n ) x 2 + · 1 + ( - 1 ) k x + ( - 1 ) k + 1 2 x 2 + = F m ( x p ) .

Mivel a jobb oldalon x 2 együtthatója 0, ezért

1 2 ( ( - 1 ) k + 1 ) - 1 + f ( n ) = 0 ,

azaz f ( n ) = 1 2 ( ( - 1 ) k + 1 + 1 ) .

Második megoldás: (1) deriváltját (1)-gyel osztva

n x n - 1 x n - 1 = ? d | n F d ' ( x ) F d ( x )

(mellesleg, ide x = 0 -t helyettesítve igazolhatjuk 4. d)-t). Ha n ? 3 , akkor a bal oldal deriváltja 0-ban 0 (miért?), így

0 = ? d | n F d ( 0 ) F d ( 0 ) - F d ' ( 0 ) 2 F d ( 0 ) 2 = ? d | n F d ( 0 ) - µ 2 ( d ) ,

míg F n ( 0 ) - µ 2 ( n ) összegzési függvénye 1-ben - 1 , 2-ben - 2 .

2. d) szerint tehát

F n ( 0 ) - µ 2 ( n ) = - µ ( n ) . ha 2 ? n , - µ ( n ) - 2 µ n 2 , ha 2 | n .

Négyzetmentes n -re

F n ( 0 ) ? { 1 - µ ( n ) , 1 + µ ( n ) } = { 0 , 2 } ,

nem négyzetmentes n -re

F n ( 0 ) ? 0 , - 2 µ n 2 ? { - 2 , 0 , 2 } .

F n -ben x 2 együtthatója 1 2 F n ( 0 ) , így készen vagyunk.

5. Minden n -edik egységgyök pontosan egy d -re primitív d -edik egységgyök, és ez a d osztja n -et. (Miért?) Tehát

? d | n ? ? primitív d -edik egységgyök ( x - ? ) = ? ? n = 1 ( x - ? ) = x n - 1 ,

és ez elég.

Ennek fényében érdemes újra megoldani a 3. a), b), c), d) feladatokat.