Kezdőlap


Feladat:	A.486	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Ágoston Tamás , Backhausz Tibor , Bodor Bertalan , Éles András , Frankl Nóra , Nagy Donát , Nagy János , Somogyi Ákos , Strenner Péter , Szabó Attila
Füzet:	2010/február, 92 - 94. oldal		PDF \| MathML
Témakör(ök):	Nehéz feladat, Euler-Fermat-tételek, Maradékosztályok
Hivatkozás(ok):	Feladatok: 2009/szeptember: A.486

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. Felhasználjuk, hogy

\begin{matrix} ν (n) = \sum_{k = 1}^{\infty} [\frac{n}{2^{k}}]; \end{matrix}

(1)

ez speciális esete az úgynevezett Legendre-formulának. (A Legendre-formuláról bővebben lásd az 1. megjegyzést.)
Ha az

n

szám kettes számrendszerbeli alakja

\begin{matrix} n = \bar{d_{ℓ} d_{ℓ - 1} ... d_{1} d_{0}} = \sum_{i = 0}^{ℓ} d_{i} \cdot 2^{i}, \end{matrix}

ahol a

d_{0}, ..., d_{ℓ}

számjegyek mindegyike

0

vagy

1

, akkor (1)-ben csak

k \leq ℓ

esetén kapunk

0

-tól különböző tagokat, és

\begin{matrix} ν (n) & = \sum_{k = 1}^{\infty} [\frac{n}{2^{k}}] = \sum_{k = 1}^{ℓ} [\frac{\bar{d_{ℓ} d_{ℓ - 1} ... d_{1} d_{0}}}{2^{k}}] = \sum_{k = 1}^{ℓ} \bar{d_{ℓ} d_{ℓ - 1} ... d_{k}} = \\ = \sum_{k = 1}^{ℓ} (\sum_{i = k}^{ℓ} d_{i} \cdot 2^{i - k}) = \sum_{i = 1}^{ℓ} d_{i} (\sum_{k = 1}^{i} 2^{i - k}) = \sum_{i = 1}^{ℓ} d_{i} \cdot (2^{i} - 1) . \end{matrix}

Ennek egyszerű következménye, hogy pontosan azok a pozitív egészek állnak elő

ν (n)

alakban, amelyek felírhatók különböző

2^{i} - 1

alakú számok összegeként.

Következő lépésként megmutatjuk, hogy van olyan

r

szám, ami relatív

m

-mel, és végtelen sokszor áll elő

2^{i} - 1

alakú számok

m

-mel való osztási maradékaként, vagyis léteznek olyan

i_{1} < i_{2} < i_{3} < ...

pozitív egészek, amelyekre

\begin{matrix} 2^{i_{1}} - 1 \equiv 2^{i_{2}} - 1 \equiv 2^{i_{3}} - 1 \equiv ... \equiv r (mod m) . \end{matrix}

Írjuk

m

-et

2^{t} u

alakban, ahol

u

páratlan szám, és tekintsünk egy tetszőleges olyan

i \geq t

pozitív egészt, amire

i - 1

osztható

φ (u)

-val. Nyilván végtelen sok ilyen

i

létezik. Az Euler‐Fermat-tétel alapján minden egyes ilyen

i

értékre

\begin{matrix} u | 2^{φ (u)} - 1 | 2^{i - 1} - 1, \\ 2^{i} - 1 = 2 (2^{i - 1} - 1) + 1 \equiv 1 (mod u), & (2) \end{matrix}

és

i \geq t

miatt

\begin{matrix} 2^{i} - 1 \equiv - 1 (mod 2^{t}) . \end{matrix}

(3)

2^{i} - 1

szám (2) és (3) miatt relatív prím

u

-val és

2^{t}

-vel is, továbbá (2) és (3) egyértelműen meghatározza

2^{i} - 1

maradékát modulo

[u, 2^{t}] = m

. Ez a maradék tehát valóban végtelen sokszor előfordul.

Mivel

m

és

r

relatív prímek, az

r,2 r,3 r, ...

számok teljes maradékrendszert alkotnak modulo

m

, és létezik olyan

u

pozitív egész, amire

a \equiv u r (mod m)

. Ekkor az

n = 2^{i_{1}} + ... + 2^{i_{u}}

számra

\begin{matrix} ν (n) = ν (2^{i_{1}} + ... + 2^{i_{u}}) = (2^{i_{1}} - 1) + ... + (2^{i_{u}} - 1) \equiv u \cdot r \equiv a (mod m) . \end{matrix}

Ezzel megkonstruáltuk a kívánt

n

számot.

Megjegyzések. 1. Ha

ν_{p} (n)

-nel jelöljük tetszőleges

p

prímszámra és nemnegatív egész

n

-re a

p

kitevőjét az

n!

prímtényezős felbontásában, akkor az úgynevezett Legendre-formula szerint

\begin{matrix} ν_{p} (n) = [\frac{n}{p}] + [\frac{n}{p^{2}}] + [\frac{n}{p^{3}}] + ... = \sum_{k = 1}^{\infty} [\frac{n}{p^{k}}] . \end{matrix}

Ha összeszámoljuk azt, hogy az

1,2, ..., n

számok között hány

p

-vel osztható, hány

p^{2}

-tel osztható stb. van, éppen a jobboldalon álló összeget kapjuk. Ez szemléletesen bizonyítja a képletet.
A formálisabb bizonyításhoz tetszőleges

ℓ

pozitív egészre jelöljük

μ_{p} (ℓ)

-lel a

p

kitevőjét az

ℓ

prímtényezős felbontásában. Mivel szorzásnál a kitevők összeadódnak,

\begin{matrix} ν_{p} (n) = μ_{p} (1 \cdot 2 \cdot ... \cdot n) = μ_{p} (1) + μ_{p} (2) + ... + μ_{p} (n) . \end{matrix}

Tekintsük most az összes olyan

(k, ℓ)

párt, amelyekben

1 \leq ℓ \leq n

és

p^{k}

osztója

ℓ

-nek, és számoljuk össze kétféleképpen az ilyen tulajdonságú párokat.
Először csoportosítsuk a

(k, ℓ)

párokat

ℓ

értékei szerint. Egy rögzített

ℓ

szám a

p

-nek mindig pontosan

μ_{p} (ℓ)

különböző hatványával osztható: ezek a

p, p^{2}, ..., p^{μ_{p} (ℓ)}

számok, ezért

\begin{matrix} \sum_{(k, ℓ)}^{} 1 = \sum_{ℓ}^{n} \sum_{p^{k} | ℓ}^{} 1 = \sum_{ℓ}^{n} μ_{p} (ℓ) = ν_{p} (n) . \end{matrix}

(4)

Most csoportosítsuk a párokat

k

értékei szerint. Minden egyes

k

-ra azokat az

ℓ

-eket keressük, amelyek többszöresei

p^{k}

-nak; az

1,2, ..., n

között ezek száma

[\frac{n}{p^{k}}]

. A párok száma tehát

\begin{matrix} \sum_{(k, ℓ)}^{} 1 = \sum_{k = 1}^{\infty} \sum_{ℓ \leq n, p^{k} | ℓ}^{} 1 = \sum_{k = 1}^{\infty} [\frac{n}{p^{k}}] . \end{matrix}

(5)

A (4) és (5) képletek együtt bizonyítják a Legendre-formulát.

2. Az állítást a

2

helyett bármelyik másik prímmel kimondhatjuk; a bizonyítás minden nehézség nélkül átírható.