Faktoriallar, rəqəmlər və Legendre düsturu — Onlayn dərslik

Qeyd. Bu dərsdə nə var. İndiyə qədər ədədləri bölənləri və qalıqları ilə öyrəndik. Bu dərsdə iki yeni «obyekt» əlavə edirik: faktorial

n!

və ədədin onluq rəqəmləri. Faktorial olimpiadada demək olar hər il çıxır, çünki o, çox böyük olmasına baxmayaraq sadə vuruqlara ayrılışı tam məlum olan nadir ifadədir. Bunu verən düstur Legendre (de Polignac) düsturudur:

\mathrm{v}_p(n!)=\Big\lfloor \tfrac{n}{p}\Big\rfloor+\Big\lfloor \tfrac{n}{p^{2}}\Big\rfloor+\Big\lfloor \tfrac{n}{p^{3}}\Big\rfloor+\cdots

Ondan sonundakı sıfırların sayı, binomial əmsalların bölünməsi (Kummer teoremi) və bir çox «

n!

tam kvadratdırmı?» tipli məsələ birbaşa çıxır. İkinci hissədə rəqəmlər cəmi ilə işləyəcəyik:

\mathrm{S}(n)\equiv n \pmod 9

münasibəti, mod

11

üçün növbələşən cəm, rəqəm kökü, rəqəmlərin sayı və son rəqəmlər. Bunlar Dərs 6-nın qalıq texnikası ilə birləşəndə çox güclü olur.

Əvvəlki dərslərdən nə lazımdır. Bölünmə və sadə vuruqlara ayrılış (Dərs 2–3),

\mathrm{v}_p

göstəricisi ilə iş (Dərs 3), konqruensiyalar və qalıq cədvəlləri (Dərs 5–6), Ferma və Vilson teoremləri (Dərs 7), modul ziddiyyəti (Dərs 10). Bu dərsdə öyrəndiklərimiz Dərs 12-də ümumi sintez üçün son alət dəstidir. 1Faktorialın sadə vuruqlara ayrılışı: Legendre düsturu

Tərif 1.1. Müsbət tam

n

üçün

n!=1\cdot 2\cdot 3\cdots n

yazılır və

0!=1

qəbul olunur.

p

sadə ədədi və sıfırdan fərqli

m

tam ədədi üçün

\mathrm{v}_p(m)

ilə

m

-in kanonik ayrılışında

p

-nin göstəricisi işarə olunur:

p^{\mathrm{v}_p(m)}\mid m

, lakin

p^{\mathrm{v}_p(m)+1}\nmid m

Qeyd.

\mathrm{v}_p

funksiyasının iki əsas xassəsini (Dərs 3) xatırlayaq:

\mathrm{v}_p(ab)=\mathrm{v}_p(a)+\mathrm{v}_p(b),\qquad \mathrm{v}_p(a+b)\ \ge\ \min\{\mathrm{v}_p(a),\mathrm{v}_p(b)\},

və sonuncuda

\mathrm{v}_p(a)\ne \mathrm{v}_p(b)

olduqda bərabərlik var. Ayrıca

a\mid b \iff \mathrm{v}_p(a)\le \mathrm{v}_p(b)

(hər

p

üçün).

Teorem 1.2 (Legendre — de Polignac düsturu). Hər

p

sadə ədədi və hər

n\ge 1

üçün

\mathrm{v}_p(n!)\;=\;\sum_{i=1}^{\infty}\left\lfloor \frac{n}{p^{i}}\right\rfloor =\left\lfloor \frac{n}{p}\right\rfloor+\left\lfloor \frac{n}{p^{2}}\right\rfloor+\left\lfloor \frac{n}{p^{3}}\right\rfloor+\cdots

Cəm sonludur:

p^{i}>n

olan bütün hədlər sıfırdır.

İsbat.

\mathrm{v}_p

toplanan olduğundan

\mathrm{v}_p(n!)=\sum_{m=1}^{n}\mathrm{v}_p(m).

İndi sağ tərəfi «sətirlərlə» yox, «sütunlarla» sayaq.

\mathrm{v}_p(m)

ədədi «

m

ədədi

p^{1}

-ə bölünür?» + «

m

ədədi

p^{2}

-yə bölünür?» +

\cdots

suallarına verilən

1/0

cavablarının cəmidir: doğrudan da

\mathrm{v}_p(m)=k

olduqda

m

ədədi

p^{1},\dots,p^{k}

-yə bölünür,

p^{k+1}

-ə isə yox, yəni cəm düz

k

olur. Beləliklə

\mathrm{v}_p(n!)=\sum_{m=1}^{n}\ \sum_{i\ge 1}[\,p^{i}\mid m\,] =\sum_{i\ge 1}\ \sum_{m=1}^{n}[\,p^{i}\mid m\,].

Daxili cəm

1,2,\dots,n

arasında

p^{i}

-yə bölünənlərin sayıdır, o isə

\lfloor n/p^{i}\rfloor

-dir. Bu da tələb olunan bərabərlikdir.

Qeyd. Praktik hesablama. Cəmi hər dəfə yenidən bölmək əvəzinə ardıcıl bölün:

n_1=\lfloor n/p\rfloor

n_2=\lfloor n_1/p\rfloor

n_3=\lfloor n_2/p\rfloor,\dots

və

\mathrm{v}_p(n!)=n_1+n_2+n_3+\cdots

. Bu,

\lfloor \lfloor n/a\rfloor /b\rfloor=\lfloor n/(ab)\rfloor

bərabərliyinə əsaslanır (Dərs 2).

Nümunə 1.1 (Legendre düsturunun birbaşa tətbiqi).

100!

ədədinin ayrılışında

2,3,5,7

sadə ədədlərinin göstəricilərini tapaq.

Həll. Ardıcıl bölmə ilə:

\begin{align*} \mathrm{v}_2(100!)&=50+25+12+6+3+1=97,\\ \mathrm{v}_3(100!)&=33+11+3+1=48,\\ \mathrm{v}_5(100!)&=20+4=24,\\ \mathrm{v}_7(100!)&=14+2=16. \end{align*}

Yəni

100!=2^{97}\cdot 3^{48}\cdot 5^{24}\cdot 7^{16}\cdots

Cavab:

97,\;48,\;24,\;16

Nəticə 1.3.

n!

ədədini bölən ən böyük

p

qüvvəti üçün həmişə

\mathrm{v}_p(n!)\;<\;\frac{n}{p-1}.

İsbat. Tam hissəni yuxarıdan qiymətləndirək:

\lfloor n/p^{i}\rfloor \le n/p^{i}

. Onda

\mathrm{v}_p(n!)\le \frac{n}{p}+\frac{n}{p^{2}}+\cdots=\frac{n}{p}\cdot\frac{1}{1-1/p}=\frac{n}{p-1}.

Bərabərlik yalnız bütün

\lfloor n/p^{i}\rfloor=n/p^{i}

olduqda mümkündür, bu isə sonsuz sayda

i

üçün ola bilməz (çünki

p^{i}>n

-dən sonra hədlər

0

-dır,

n/p^i

isə

0

deyil). Deməli bərabərsizlik ciddidir.

Teorem 1.4 (Rəqəmlər cəmi ilə ifadə).

n

-in

p

əsasında yazılışındakı rəqəmlərin cəmini

\mathrm{S}_p(n)

ilə işarə edək. Onda

\boxed{\ \mathrm{v}_p(n!)=\frac{n-\mathrm{S}_p(n)}{p-1}\ }

İsbat.

n=a_k p^{k}+a_{k-1}p^{k-1}+\cdots+a_1 p+a_0

olsun, burada

0\le a_j\le p-1

. Onda

\left\lfloor \frac{n}{p^{i}}\right\rfloor=a_k p^{k-i}+a_{k-1}p^{k-i-1}+\cdots+a_i,

çünki

p^{i}

-yə bölərkən sadəcə son

i

rəqəm atılır. Bunları

i=1,\dots,k

üzrə toplayaq və hər

a_j

-nin neçə dəfə hansı əmsalla iştirak etdiyinə baxaq:

a_j

rəqəmi

i=1,2,\dots,j

hədlərində

p^{j-i}

əmsalı ilə görünür, yəni ümumi payı

a_j\left(p^{j-1}+p^{j-2}+\cdots+p+1\right)=a_j\cdot\frac{p^{j}-1}{p-1}.

Deməli

\mathrm{v}_p(n!)=\sum_{j=0}^{k}a_j\cdot\frac{p^{j}-1}{p-1}=\frac{1}{p-1}\left(\sum_{j=0}^{k}a_j p^{j}-\sum_{j=0}^{k}a_j\right)=\frac{n-\mathrm{S}_p(n)}{p-1}.

Nümunə 1.2 (Düsturun sınağı).

\mathrm{v}_2(100!)

və

\mathrm{v}_5(1000!)

qiymətlərini rəqəmlər cəmi düsturu ilə hesablayaq.

Həll.

100=(1100100)_2

, deməli

\mathrm{S}_2(100)=3

və

\mathrm{v}_2(100!)=\frac{100-3}{2-1}=97.

1000=(13000)_5

, çünki

1000=1\cdot 625+3\cdot 125

. Deməli

\mathrm{S}_5(1000)=1+3=4

və

\mathrm{v}_5(1000!)=\frac{1000-4}{5-1}=\frac{996}{4}=249.

Hər ikisi ardıcıl bölmə ilə alınan cavabla üst-üstə düşür. Cavab:

97

və

249

Hansı düsturu seçmək.

• Konkret ədəd üçün ( $100!$ , $2026!$ ) — ardıcıl bölmə daha sürətlidir.
• $n$ ümumi olduqda və ya $\mathrm{v}_p$ -nin $2$ -yə bölünməsi kimi suallarda — $\dfrac{n-\mathrm{S}_p(n)}{p-1}$ düsturu daha güclüdür, çünki $n$ ilə rəqəmləri arasında birbaşa körpü qurur.
• İki faktorialın nisbətində ( $\binom{n}{k}$ kimi) — Kummer teoremi (§3) bütün işi görür.

2Sonundakı sıfırlar

Teorem 2.1.

n!

ədədinin onluq yazılışının sonundakı sıfırların sayı

\mathrm{v}_5(n!)

-ə bərabərdir.

İsbat. Sonundakı sıfırların sayı

\mathrm{v}_{10}(n!)=\min\{\mathrm{v}_2(n!),\mathrm{v}_5(n!)\}

-dir, çünki

10=2\cdot 5

. Hər

i

üçün

\lfloor n/2^{i}\rfloor \ge \lfloor n/5^{i}\rfloor

olduğundan

\mathrm{v}_2(n!)\ge \mathrm{v}_5(n!)

, deməli minimum

\mathrm{v}_5(n!)

-dir.

Nümunə 2.1 (Klassik hesablama).

2026!

ədədinin sonunda neçə sıfır var?

Həll.

\mathrm{v}_5(2026!)=\left\lfloor\frac{2026}{5}\right\rfloor+\left\lfloor\frac{2026}{25}\right\rfloor+\left\lfloor\frac{2026}{125}\right\rfloor+\left\lfloor\frac{2026}{625}\right\rfloor=405+81+16+3=505.

Cavab:

505

Nümunə 2.2 (Tərs məsələ). Sonunda düz

100

sıfır olan

n!

varmı? Varsa, bütün belə

n

-ləri tapın.

Həll.

f(n)=\mathrm{v}_5(n!)

funksiyası azalmayan pilləli funksiyadır və

n

-dən

n+1

-ə keçəndə ancaq

5\mid n+1

olduqda sıçrayır. Təxmin üçün

f(n)\approx n/4

, yəni

n\approx 400

n=400

80+16+3=99

n=405

81+16+3=100

. Deməli

f(405)=100

. Növbəti sıçrayış

n=410

-da olur:

82+16+3=101

. Beləliklə

f(n)=100

olan

n

-lər

405,406,407,408,409

-dur. Cavab:

n\in\{405,406,407,408,409\}

Qeyd. Diqqət — «boşluqlar». Hər tam ədəd

f

-in qiyməti olmur.

n

ədədi

5

-in qüvvətindən keçəndə sıçrayış

1

-dən böyük olur: məsələn

f(24)=4

f(25)=6

— yəni sonunda düz

5

sıfır olan faktorial yoxdur. Ümumi qayda:

f

-in qiymətlər çoxluğunda buraxılan ədədlər məhz

\mathrm{v}_5

-in

\ge 2

sıçradığı yerlərdə yaranır. «Sonunda düz

k

sıfır olan

n!

varmı?» tipli məsələdə əvvəlcə həmişə sıçrayışı yoxlayın.

Nümunə 2.3 (Sıçrayış tələsi). Sonunda düz

2025

sıfır olan bir

n!

varmı?

Həll.

n\approx 4\cdot 2025=8100

təxminindən başlayaq.

f(8100)=1620+324+64+12+2=2022.

f(8105)=1621+324+64+12+2=2023

f(8110)=1622+324+64+12+2=2024

f(8115)=1623+324+64+12+2=2025

. Deməli

n=8115,\dots,8119

üçün sonda düz

2025

sıfır var. Cavab: Bəli:

n\in\{8115,\dots,8119\}

«Sonundakı sıfır» məsələlərinin sxemi.

1. Sıfırların sayı $=\mathrm{v}_5(n!)$ — $2$ -ni heç vaxt saymayın.
2. Tərs məsələdə $n\approx 4k$ təxmini ilə başlayın ( $f(n)\approx n/4$ ).
3. Cavabı $5$ -in qatlarında dəqiqləşdirin: $f$ yalnız orada dəyişir.
4. Cavab çoxluğu ya boşdur, ya da ardıcıl $5$ ədəddən ibarətdir — başqa variant yoxdur.

Nümunə 2.4 (Son sıfır olmayan rəqəm).

25!

ədədinin sonundakı sıfırları atsaq, qalan ədədin son rəqəmi nədir?

Həll.

\mathrm{v}_5(25!)=5+1=6

\mathrm{v}_2(25!)=12+6+3+1=22

. Deməli

25!=2^{22}\cdot 5^{6}\cdot M=10^{6}\cdot 2^{16}\cdot M,

burada

M

ədədi

2

-yə və

5

-ə bölünmür. Bizə

2^{16}M \bmod 10

lazımdır; bu ədəd cütdür və

5

-ə bölünmür, ona görə mod

10

üçün mod

5

kifayətdir.

25!/5^{6}

ifadəsini mod

5

hesablayaq.

1,\dots,25

ədədlərini iki qrupa ayıraq.(a) $5$ -ə bölünməyənlər. Hər ardıcıl beşlik blokda (

1

–

5

6

–

10

, …)

5

-ə bölünməyən dörd ədəd var və onların hasili mod

5

-də

1\cdot 2\cdot 3\cdot 4=24\equiv -1

verir. Beş belə blok olduğuna görə bu qrupun ümumi payı

(-1)^{5}=-1

.(b) $5$ -ə bölünənlər:

5, 10, 15, 20, 25

. Onların hasili

5\cdot 10\cdot 15\cdot 20\cdot 25=5^{5}\cdot(1\cdot2\cdot3\cdot4\cdot5)=5^{5}\cdot 120=5^{6}\cdot 24.

İki qrupu birləşdirsək

25!=5^{6}\cdot 24\cdot(\text{birinci qrupun hasili})

və

\frac{25!}{5^{6}}\equiv 24\cdot(-1)\equiv 4\cdot 4=16\equiv 1 \pmod 5.

İndi

25!/10^{6}=\dfrac{25!/5^{6}}{2^{6}}

. Mod

5

-də

2^{6}=64\equiv 4

, onun tərsi

4

-dür (

4\cdot4=16\equiv1

). Deməli

\frac{25!}{10^{6}}\equiv 1\cdot 4\equiv 4 \pmod 5.

Bu ədəd cütdür (çünki

\mathrm{v}_2=22>6

), mod

10

-da cüt və mod

5

-də

4

olan yeganə qalıq

4

-dür. Cavab:

4

3Binomial əmsallar və Kummer teoremi

Tərif 3.1.

0\le k\le n

üçün binomial əmsal

\binom{n}{k}=\frac{n!}{k!\,(n-k)!}

kimi təyin olunur.

Teorem 3.2.

\binom{n}{k}

həmişə tam ədəddir.

İsbat. Hər

p

sadə ədədi üçün

\mathrm{v}_p\big(n!\big)\ge \mathrm{v}_p\big(k!\big)+\mathrm{v}_p\big((n-k)!\big)

olduğunu göstərmək kifayətdir. Legendre düsturu ilə bu, hər

i

üçün

\left\lfloor \frac{n}{p^{i}}\right\rfloor \ \ge\ \left\lfloor \frac{k}{p^{i}}\right\rfloor+\left\lfloor \frac{n-k}{p^{i}}\right\rfloor

bərabərsizliyinə çevrilir. Ümumiyyətlə hər

x,y

həqiqi ədədləri üçün

\lfloor x\rfloor+\lfloor y\rfloor \le \lfloor x+y\rfloor

doğrudur (tam hissələr atılan kəsr hissələr

\ge 0

olduğu üçün). Burada

x=k/p^{i}

y=(n-k)/p^{i}

götürmək kifayətdir.

Nəticə 3.3. İstənilən

k

ardıcıl tam ədədin hasili

k!

-ə bölünür. Doğrudan da

(m+1)(m+2)\cdots(m+k)=\frac{(m+k)!}{m!}=k!\cdot\binom{m+k}{k}.

Teorem 3.4 (Kummer).

p

sadə,

0\le k\le n

olsun. Onda

\mathrm{v}_p\!\left(\dbinom{n}{k}\right)

ədədi

k

ilə

n-k

ədədlərini

p

əsasında sütun-sütun toplayarkən baş verən keçidlərin (onluğa köçürmələrin) sayına bərabərdir.

İsbat. Rəqəmlər cəmi düsturundan

\mathrm{v}_p\binom{n}{k}=\frac{n-\mathrm{S}_p(n)}{p-1}-\frac{k-\mathrm{S}_p(k)}{p-1}-\frac{(n-k)-\mathrm{S}_p(n-k)}{p-1} =\frac{\mathrm{S}_p(k)+\mathrm{S}_p(n-k)-\mathrm{S}_p(n)}{p-1}.

İndi

k

ilə

n-k

-nı

p

əsasında toplayaq. Keçid olmayan hər sütunda rəqəmlər sadəcə toplanır və rəqəmlər cəmi dəyişmir. Hər keçiddə isə cari sütundan

p

çıxılır və növbəti sütuna

1

əlavə olunur, yəni ümumi rəqəmlər cəmi düz

p-1

azalır. Deməli

c

keçid varsa,

\mathrm{S}_p(k)+\mathrm{S}_p(n-k)-\mathrm{S}_p(n)=c\,(p-1),

buradan

\mathrm{v}_p\binom{n}{k}=c

Nümunə 3.1 (Kummer teoremi işdə).

\dbinom{1000}{500}

ədədi

3

-ün hansı ən böyük qüvvətinə bölünür?

Həll. Əvvəlcə

500

-ü

3

əsasında yazaq:

500=2\cdot 243+1\cdot 9+1\cdot 3+2

, yəni

500=(2\,0\,0\,1\,1\,2)_3.

İndi

500+500

toplamasını

3

əsasında sütun-sütun aparaq (sağdan sola; «k» keçid deməkdir):

\begin{array}{c|cccccc} \text{sütun} & 5 & 4 & 3 & 2 & 1 & 0\\\hline \text{rəqəm} & 2 & 0 & 0 & 1 & 1 & 2\\ \text{cəm}+\text{keçid} & 4 & 0 & 1 & 3 & 3 & 4\\ \text{keçid?} & \text{k} & - & - & \text{k} & \text{k} & \text{k} \end{array}

Ümumilikdə

4

keçid var, deməli

\mathrm{v}_3\dbinom{1000}{500}=4

. Legendre ilə yoxlama.

\mathrm{v}_3(1000!)=333+111+37+12+4+1=498,\qquad \mathrm{v}_3(500!)=166+55+18+6+2=247,

buradan

498-2\cdot 247=4

. İki üsul üst-üstə düşür. Cavab:

3^{4}\,\|\,\dbinom{1000}{500}

Qeyd. Kummer nə üçün faydalıdır. Legendre ilə cavab tapmaq üçün iki uzun cəm hesablamaq lazım gəlir və hər hansı həddi unutmaq asandır. Kummer isə yalnız keçidləri saymağı tələb edir — bu, həm daha sürətlidir, həm də

n

ümumi olduqda (

n=2^{k}

n=p^{k}-1

və s.) birbaşa nəticə verir. Bir hesablamanı digəri ilə yoxlamaq isə səhvi dərhal üzə çıxarır.

Nəticə 3.5.

p

sadə və

0<k<p

olarsa,

p\mid \dbinom{p}{k}

İsbat.

p

əsasında

p=(10)_p

-dir.

k

və

p-k

ədədlərinin hər ikisi

p

-dən kiçik olduğundan onlar birrəqəmlidir və

k+(p-k)=p

toplaması sıfırıncı sütunda mütləq keçid verir. Deməli ən azı bir keçid var, yəni

\mathrm{v}_p\binom{p}{k}\ge 1

Nəticə 3.6 (Freshman’s dream).

p

sadə olarsa, hər

a,b

tam ədədləri üçün

(a+b)^{p}\equiv a^{p}+b^{p} \pmod p

İsbat. Nyuton binomu ilə açsaq,

0<k<p

olan bütün hədlərin əmsalı

\binom{p}{k}

-dır və yuxarıdakı nəticəyə görə

p

-yə bölünür. Yalnız

k=0

və

k=p

hədləri qalır. (Bu, Fermanın kiçik teoreminin induksiya ilə isbatının özəyidir — Dərs 7.)

Teorem 3.7 (Mərkəzi binomial əmsalın

2

göstəricisi). Hər

n\ge 1

üçün

\mathrm{v}_2\!\left(\binom{2n}{n}\right)=\mathrm{S}_2(n),

yəni

n

-in ikilik yazılışındakı vahidlərin sayına bərabərdir. Xüsusi halda

\binom{2n}{n}

həmişə cütdür, və o,

2

-yə düz bir dəfə bölünür yalnız və yalnız

n

ikinin qüvvəti olduqda.

İsbat. Kummer teoremini

p=2

k=n

üçün tətbiq edək:

n+n

toplamasındakı keçidlərin sayı lazımdır. Alternativ olaraq rəqəmlər cəmi düsturu ilə:

\mathrm{v}_2\binom{2n}{n}=\frac{\mathrm{S}_2(n)+\mathrm{S}_2(n)-\mathrm{S}_2(2n)}{2-1}=2\mathrm{S}_2(n)-\mathrm{S}_2(2n)=2\mathrm{S}_2(n)-\mathrm{S}_2(n)=\mathrm{S}_2(n),

çünki

2n

-in ikilik yazılışı

n

-inkinə bir sıfır əlavə etməklə alınır, rəqəmlər cəmi isə dəyişmir.

\mathrm{S}_2(n)\ge 1

olduğundan

\binom{2n}{n}

cütdür;

\mathrm{S}_2(n)=1

isə məhz

n=2^{t}

deməkdir.

Nümunə 3.2 (Bölünmə sualı).

\dbinom{2^{k}}{j}

əmsalı bütün

0<j<2^{k}

üçün cütdürmü?

Həll.

n=2^{k}

ikilik yazılışda

1

və ardınca

k

dənə

0

-dır.

j+(2^{k}-j)=2^{k}

toplamasında

0<j<2^{k}

olduğundan hər iki toplanan

k

rəqəmlik (və ya daha qısa) olur, nəticə isə

k+1

rəqəmlikdir — deməli ən azı bir keçid mütləq baş verir. Kummer ilə

\mathrm{v}_2\binom{2^{k}}{j}\ge 1

. Cavab: Bəli, hamısı cütdür

Faktorial-bölünmə məsələlərinin iş sxemi.

1. Sual « $n!$ -i $p^{a}$ bölürmü?» şəklindədirsə — Legendre cəmi.
2. Sual binomial əmsal və ya çoxhədli əmsal haqqındadırsa — Kummer (keçid sayımı) daha sürətlidir.
3. Sual « $n!$ tam kvadratdırmı / tam kubdurmu?» şəklindədirsə — bir sadə ədəd seçib $\mathrm{v}_p(n!)$ -in tək olduğunu göstərməyə çalışın (Bertran postulatı: $n\ge 2$ üçün $n<p\le 2n$ aralığında sadə ədəd var).
4. Sual « $\dfrac{a!\,b!}{c!}$ tam ədəddirmi?» şəklindədirsə — hər $p$ üçün Legendre cəmlərini müqayisə edin, çox vaxt $\lfloor x\rfloor+\lfloor y\rfloor\le\lfloor x+y\rfloor$ bərabərsizliyi bütün işi görür.

Nümunə 3.3 (Klassik:

n!

nə vaxt tam kvadratdır).

n!

ifadəsinin tam kvadrat olduğu bütün

n\ge 1

qiymətlərini tapın.

Həll.

n=1

1!=1=1^{2}

— uyğundur.

n=2,3

2,6

— kvadrat deyil.

n\ge 4

olsun. Bertran postulatına görə

\lceil n/2\rceil \le p\le n

aralığında elə

p

sadə ədədi var ki,

n<2p

. Onda

1,\dots,n

arasında

p

-nin qatları yalnız

p

özüdür (çünki

2p>n

), və

p^{2}>n

olduğundan Legendre cəmində yalnız birinci həd qalır:

\mathrm{v}_p(n!)=\left\lfloor \frac{n}{p}\right\rfloor=1.

Tam kvadratda hər sadə ədədin göstəricisi cüt olmalıdır,

1

isə təkdir. Ziddiyyət. Cavab: Yalnız

n=1

4Rəqəmlər cəmi, mod 9 və mod 11

Tərif 4.1.

n

müsbət tam ədədinin onluq yazılışı

n=\overline{a_k a_{k-1}\ldots a_1 a_0}

olsun. Onda

\mathrm{S}(n)=a_k+a_{k-1}+\cdots+a_0

rəqəmlər cəmi,

\mathrm{S}^{\pm}(n)=a_0-a_1+a_2-a_3+\cdots

isə növbələşən rəqəmlər cəmidir.

Teorem 4.2. Hər

n

üçün

n\equiv \mathrm{S}(n)\pmod 9,\qquad n\equiv \mathrm{S}^{\pm}(n)\pmod{11}.

İsbat.

n=\sum_j a_j 10^{j}

və

10\equiv 1 \pmod 9

olduğundan

10^{j}\equiv 1

, deməli

n\equiv \sum_j a_j=\mathrm{S}(n)

. Mod

11

-də isə

10\equiv -1

, deməli

10^{j}\equiv(-1)^{j}

və

n\equiv \sum_j (-1)^{j}a_j=\mathrm{S}^{\pm}(n)

Nəticə 4.3.

3\mid n \iff 3\mid \mathrm{S}(n)

;

\ 9\mid n \iff 9\mid \mathrm{S}(n)

;

\ 11\mid n \iff 11\mid \mathrm{S}^{\pm}(n)

Xassə 4.4. Rəqəmlər cəminin işlədilməsində üç faydalı fakt:

1. $\mathrm{S}(n)\le 9\cdot(\text{rəqəmlərin sayı})=9\big(\lfloor \log_{10}n\rfloor+1\big)$ — yəni $\mathrm{S}(n)$ $n$ -dən çox-çox kiçikdir.
2. $\mathrm{S}(a+b)\le \mathrm{S}(a)+\mathrm{S}(b)$ və $\mathrm{S}(ab)\le \mathrm{S}(a)\mathrm{S}(b)$ .
3. $\mathrm{S}(n)\equiv n \pmod 9$ olduğundan $\mathrm{S}(\mathrm{S}(n))\equiv n$ , $\mathrm{S}(\mathrm{S}(\mathrm{S}(n)))\equiv n\pmod 9$ və s.

Tərif 4.5.

n\ge 1

ədədinin rəqəm kökü

\mathrm{dr}(n)

— rəqəmlər cəmini təkrar-təkrar alaraq alınan birrəqəmli ədəddir. Yuxarıdakı xassədən

\mathrm{dr}(n)=\begin{cases} 9, & 9\mid n,\\ n \bmod 9, & \text{əks halda.}\end{cases}

Nümunə 4.1 (Təkrar rəqəmlər cəmi).

A=4444^{4444}

ədədinin rəqəmlər cəmi

B

B

-nin rəqəmlər cəmi isə

C

-dir.

C

-nin rəqəmlər cəmini tapın. (IMO 1975)

Həll. Yuxarıdan qiymətləndirmə.

4444^{4444}<10000^{4444}=10^{17776}

, deməli

A

-nın ən çoxu

17776

rəqəmi var və

B=\mathrm{S}(A)\le 9\cdot 17776=159\,984.

B\le 159984

olduğundan

B

-nin ən çoxu

6

rəqəmi var, üstəlik

B\le 159984

aralığında rəqəmlər cəmi ən böyük

99999

-da alınır:

C=\mathrm{S}(B)\le \mathrm{S}(99999)=45.

Nəhayət

C\le 45

olduğundan

\mathrm{S}(C)\le \mathrm{S}(39)=12

. Mod $9$ .

4444\equiv 4+4+4+4=16\equiv 7 \pmod 9

7

-nin qüvvətləri mod

9

7,4,1,7,4,1,\dots

— dövr

3

4444=3\cdot1481+1

, deməli

4444^{4444}\equiv 7^{1}\equiv 7 \pmod 9

. Bütün rəqəmlər cəmləri mod

9

-da eyni qalıq verir, deməli

\mathrm{S}(C)\equiv 7\pmod 9

\mathrm{S}(C)\le 12

olduğundan yeganə imkan

\mathrm{S}(C)=7

. Cavab:

7

«Rəqəmlər cəmi» məsələlərinin iki sütunu. Bu tip məsələlərin demək olar hamısı iki addımın birləşməsidir:

1. Sərhəd: rəqəmlərin sayı $\le \log_{10}$ qiymətləndirməsi ilə $\mathrm{S}$ -nin nə qədər kiçildiyini göstərin.
2. İnvariant: $\mathrm{S}(n)\equiv n \pmod 9$ (lazım gələrsə mod $11$ ) — bu, bütün addımlarda dəyişməyən yeganə məlumatdır.

Sərhəd cavabı kiçik bir çoxluğa salır, invariant isə o çoxluqdan yeganəsini seçir.

Nümunə 4.2 (İnvariant ilə «ola bilməz»). Rəqəmləri yalnız

1

-lərdən ibarət olan

\underbrace{11\ldots1}_{n}

(

n\ge 2

) ədədinin tam kvadrat olmadığını isbat edin.

Həll. Bu ədəd təkdir, deməli kvadratı olsaydı, tək ədədin kvadratı olardı. Tək ədədin kvadratı mod

4

-də həmişə

1

verir. Digər tərəfdən son iki rəqəm

11

-dir və

n\ge 2

üçün

\underbrace{11\ldots1}_{n}\equiv 11\equiv 3 \pmod 4.

3\ne 1

, ziddiyyət.

Nümunə 4.3 (Rəqəmlərin yerdəyişməsi).

n

və

2n

ədədlərinin rəqəmləri eyni çoxluğu (təkrarlarla) təşkil edirsə,

9\mid n

olduğunu isbat edin.

Həll. Rəqəmlər eyni olduğundan

\mathrm{S}(2n)=\mathrm{S}(n)

. Onda mod

9

-da

2n\equiv \mathrm{S}(2n)=\mathrm{S}(n)\equiv n \pmod 9 \ \Longrightarrow\ n\equiv 0\pmod 9.

Teorem 4.6 (Rəqəmlərin sayı).

n\ge 1

ədədinin onluq yazılışında

\lfloor \log_{10}n\rfloor+1

rəqəm var. Xüsusi halda

10^{k-1}\le n<10^{k}

olması

n

-in düz

k

rəqəmli olması deməkdir.

Nümunə 4.4 (Neçə rəqəm).

2^{1000}

ədədində neçə rəqəm var? (

\log_{10}2\approx 0{,}30103

)

Həll.

\log_{10}2^{1000}=1000\cdot 0{,}30103=301{,}03

. Deməli

\lfloor 301{,}03\rfloor+1=302

. Cavab:

302

Qeyd. Son rəqəmlər. «

N

-in son rəqəmi» sualı

N \bmod 10

, «son iki rəqəmi» sualı

N \bmod 100

deməkdir. Bunlar Dərs 6–7-nin işidir:

\bmod\ 10

üçün qüvvətlərin dövrü

\le 4

\bmod\ 100

üçün isə

\varphi(100)=40

(Euler). Çin qalıq teoremi ilə (Dərs 8)

\bmod\ 100

-ü

\bmod\ 4

və

\bmod\ 25

-ə ayırmaq çox vaxt daha rahatdır.

Nümunə 4.5 (Son iki rəqəm).

7^{2026}

ədədinin son iki rəqəmini tapın.

Həll.

\bmod\ 4

7\equiv -1

, deməli

7^{2026}\equiv(-1)^{2026}=1

\bmod\ 25

\varphi(25)=20

və

\mbox{ƏBOB}(7,25)=1

, deməli

7^{20}\equiv 1

2026=20\cdot101+6

, buradan

7^{2026}\equiv 7^{6}

. Hesablayaq:

7^{2}=49\equiv -1 \pmod{25}

, deməli

7^{6}=(7^{2})^{3}\equiv(-1)^{3}=-1\equiv 24

. İndi ÇQT:

x\equiv 1 \pmod 4

x\equiv 24\pmod{25}

x=24+25t

24+25t\equiv 1 \pmod 4 \Rightarrow 0+t\equiv 1

t\equiv 1

t=1

x=49

. Cavab:

49

5Faktorial iştirak edən tənliklər

Faktorial tənliklərinin üç açarı.

1. Sürətli artım. $n!$ eksponensialdan da sürətli artır: $n\ge 4$ üçün $n!>2^{n}$ , $n\ge 7$ üçün $n!>n^{3}$ . Deməli tənliyin böyük $n$ -lərdə həlli olmadığını sərhədləmə ilə göstərmək çox vaxt asandır — qalan kiçik hallar əl ilə yoxlanır.
2. Modul kilidləri. $n\ge k$ olduqda $k\mid n!$ . Yəni böyük $n$ -lər üçün $n!\equiv 0$ istənilən sabit modulda. Bu, « $n!+c$ » tipli ifadələri modulda tam sabitləşdirir.
3. Legendre. Sual kvadrat/kub olmaqla bağlıdırsa, $\mathrm{v}_p$ -nin cütlüyünə baxın (Bertran postulatı ilə uyğun $p$ seçin).

Nümunə 5.1 (Kiçik faktorial tənliyi).

n!+2

ifadəsinin tam kvadrat olduğu bütün müsbət tam

n

qiymətlərini tapın.

Həll. Kiçik hallar:

n=1

3

— yox.

n=2

4=2^{2}

— bəli.

n=3

8

— yox.

n\ge 4

olsun. Onda

4\mid n!

, deməli

n!+2\equiv 2 \pmod 4

. Tam kvadrat mod

4

-də yalnız

0

və ya

1

ola bilər. Ziddiyyət. Cavab:

n=2

Nümunə 5.2 (Bir az daha çətini).

n!+1

ifadəsinin tam kvadrat olduğu

n\le 10

qiymətlərini tapın.

Həll. Birbaşa hesablayaq:

1!+1=2

2!+1=3

3!+1=7

4!+1=25=5^{2}

(bəli),

5!+1=121=11^{2}

(bəli),

6!+1=721=7\cdot 103

7!+1=5041=71^{2}

(bəli),

8!+1=40321=61\cdot 661

9!+1=362881=19\cdot 71\cdot 269

10!+1=3628801=11\cdot 329891

. Cavab:

n=4,5,7

Qeyd. Sonuncu məsələ Brokar məsələsi kimi tanınır:

n!+1=m^{2}

tənliyinin

n=4,5,7

-dən başqa həllinin olub-olmadığı bu günə qədər açıq problemdir. Olimpiadada belə sual həmişə məhdud aralıqla verilir — «bütün

n

-ləri tapın» yazılıbsa, çox güman ki, məsələ başqadır. Şərti diqqətlə oxuyun.

Nümunə 5.3 (Cəm faktorial).

1!+2!+3!+\cdots+n!

cəminin tam kvadrat olduğu bütün

n

qiymətlərini tapın.

Həll. Cəmi

T_n

ilə işarə edək.

T_1=1=1^{2}

(bəli),

T_2=3

T_3=9=3^{2}

(bəli),

T_4=33

n\ge 4

olsun.

5\mid k!

(hər

k\ge 5

üçün), deməli

T_n\equiv T_4=33\equiv 3 \pmod 5.

Tam kvadrat mod

5

-də yalnız

0,1,4

ola bilər.

3

bu siyahıda yoxdur — ziddiyyət. Cavab:

n=1

və

n=3

Nümunə 5.4 (Faktorialların bərabərliyi).

x!+y!=z!

tənliyinin bütün müsbət tam həllərini tapın.

Həll. Simmetriyaya görə

x\le y

qəbul edək. Onda

z!>y!

, deməli

z\ge y+1

və

z!\ \ge\ (y+1)!=(y+1)\cdot y!.

Digər tərəfdən

x!+y!\le 2\cdot y!

. Deməli

(y+1)\,y!\le 2\,y!

, buradan

y+1\le 2

, yəni

y=1

. Onda

x=1

və

1+1=2=2!

, yəni

z=2

. Cavab:

(x,y,z)=(1,1,2)

Nümunə 5.5 (Legendre ilə bölünmə).

\dfrac{(2m)!\,(2n)!}{m!\,n!\,(m+n)!}

ifadəsinin hər

m,n\ge 0

üçün tam ədəd olduğunu isbat edin. (Putnam 1972)

Həll. Hər

p

sadə ədədi və hər

i\ge 1

üçün

x=m/p^{i}

y=n/p^{i}

qoyub aşağıdakı bərabərsizliyi isbat etmək kifayətdir:

\lfloor 2x\rfloor+\lfloor 2y\rfloor\ \ge\ \lfloor x\rfloor+\lfloor y\rfloor+\lfloor x+y\rfloor.

Doğrudan da, bu bərabərsizliyi bütün

i

üzrə toplasaq, Legendre düsturuna görə

\mathrm{v}_p\big((2m)!\big)+\mathrm{v}_p\big((2n)!\big)\ \ge\ \mathrm{v}_p(m!)+\mathrm{v}_p(n!)+\mathrm{v}_p\big((m+n)!\big),

yəni surət məxrəcə bölünür. Bərabərsizliyi isbat edək.

x=\lfloor x\rfloor+\alpha

y=\lfloor y\rfloor+\beta

olsun,

0\le\alpha,\beta<1

. Onda

\lfloor 2x\rfloor=2\lfloor x\rfloor+\lfloor 2\alpha\rfloor,\quad \lfloor 2y\rfloor=2\lfloor y\rfloor+\lfloor 2\beta\rfloor,\quad \lfloor x+y\rfloor=\lfloor x\rfloor+\lfloor y\rfloor+\lfloor \alpha+\beta\rfloor.

Deməli isbat ediləcək bərabərsizlik

\lfloor 2\alpha\rfloor+\lfloor 2\beta\rfloor\ \ge\ \lfloor \alpha+\beta\rfloor

şəklinə düşür. Sağ tərəf

0

və ya

1

-dir. Əgər

\lfloor\alpha+\beta\rfloor=1

olarsa,

\alpha+\beta\ge 1

, deməli

\alpha

və

\beta

-dan heç olmasa biri

\ge 1/2

-dir və uyğun

\lfloor 2\cdot\rfloor

həddi

\ge 1

olur. Hər iki halda bərabərsizlik doğrudur.

Nümunə 5.6 (Katalan ədədlərinin tamlığı).

\dfrac{(2n)!}{n!\,(n+1)!}

ifadəsinin hər

n\ge 0

üçün tam ədəd olduğunu göstərin. (Katalan ədədləri)

Həll. Sadə cəbri yol:

\frac{(2n)!}{n!\,(n+1)!}=\frac{1}{n+1}\binom{2n}{n}=\binom{2n}{n}-\binom{2n}{n+1},

çünki

\binom{2n}{n}-\binom{2n}{n+1}=\frac{(2n)!}{n!\,n!}-\frac{(2n)!}{(n+1)!\,(n-1)!} =\frac{(2n)!}{n!\,(n+1)!}\Big((n+1)-n\Big)=\frac{(2n)!}{n!\,(n+1)!}.

İki tam ədədin fərqi tam ədəddir.

6İş sxemi, tipik səhvlər və cib cədvəli

Faktorial/rəqəm məsələsinə yanaşma sxemi.

1. Obyekti tanı. Faktorial varmı? Rəqəmlər varmı? Hər ikisi varmı?
2. Faktorial varsa: sual bölünmə haqqındadırsa $\to$ Legendre/Kummer; sual kvadrat-kub haqqındadırsa $\to$ $\mathrm{v}_p$ -nin cütlüyü + Bertran; tənlikdirsə $\to$ artım sürəti ilə sərhədləyib kiçik halları yoxla.
3. Rəqəmlər varsa: $\mathrm{S}(n)\equiv n \pmod 9$ invariantını dərhal yaz; rəqəmlərin sayı üçün $\log_{10}$ sərhədini qur; son rəqəmlər üçün mod $10,100,1000$ -ə keç.
4. Hər ikisi varsa: əvvəlcə faktorialı modda «öldür» ( $n\ge k \Rightarrow k\mid n!$ ), sonra rəqəm invariantını tətbiq et.
5. Cavabı yoxla: kiçik $n$ -lər üçün əl ilə hesabla — faktorial məsələlərində sərhəd səhvi ən çox rast gəlinən xətadır.

Qeyd. Tipik səhvlər.

1. Legendre cəmində həd unutmaq. $\mathrm{v}_5(1000!)=200+40+8+1=249$ — dördüncü həd ( $\lfloor 1000/625\rfloor=1$ ) tez-tez unudulur. Qayda: $p^{i}>n$ olana qədər davam edin.
2. Sonundakı sıfırları $\mathrm{v}_2$ ilə saymaq. Sıfırların sayı həmişə $\mathrm{v}_5$ -dir, çünki $2$ -lər həmişə artıqlaması ilə var.
3. «Hər $k$ üçün $\mathrm{v}_5(n!)=k$ olan $n$ var» zənn etmək. $5$ -in qüvvətlərində sıçrayış $\ge 2$ olur; məsələn düz $5$ sıfırla bitən faktorial yoxdur.
4. $\mathrm{S}(n)$ -i mod $3$ ilə qarışdırmaq. $\mathrm{S}$ invariantı mod $9$ üçün işləyir; mod $3$ onun zəif halıdır. Mod $11$ üçün növbələşən cəm lazımdır, adi cəm yox.
5. Kiçik halları unutmaq. « $n\ge 4$ üçün ziddiyyət» tapıb $n=1,2,3$ -ü yoxlamamaq — cavabın yarısını itirmək deməkdir.
6. $\binom{n}{k}$ -nın tam olmasını «aydındır» saymaq. Olimpiadada bu, isbat tələb edən addımdır; Legendre və ya kombinator arqument yazın.
7. Brokar tələsi. $n!+1=m^{2}$ tipli tənlikdə «bütün həlləri tapın» sualına tam cavab yoxdur — şərtdəki aralığa diqqət edin.

Qeyd. Cib cədvəli.

$\mathrm{v}_p(n!)$	$\displaystyle\sum_{i\ge1}\lfloor n/p^{i}\rfloor=\frac{n-\mathrm{S}_p(n)}{p-1}$
$n!$ -in sonundakı sıfırlar	$\mathrm{v}_5(n!)$
$\mathrm{v}_p\binom{n}{k}$	$k+(n-k)$ toplamasında $p$ əsasında keçidlərin sayı
$\mathrm{v}_2\binom{2n}{n}$	$\mathrm{S}_2(n)$ — $n$ -in ikilikdəki vahidlərinin sayı
$n\bmod 9$	$\mathrm{S}(n)\bmod 9$
$n\bmod 11$	$\mathrm{S}^{\pm}(n)\bmod 11$
rəqəmlərin sayı	$\lfloor\log_{10}n\rfloor+1$
$k$ ardıcıl ədədin hasili	$k!$ -ə bölünür
$n$ tərkib və $n\ne 4$ $\Rightarrow$	$n\mid (n-1)!$ (Vilson teoreminin əksi, Dərs 7)

7Asan məsələlər

Məsələ 1.

50!

ədədinin sonunda neçə sıfır var?

Həll.

\mathrm{v}_5(50!)=\left\lfloor\frac{50}{5}\right\rfloor+\left\lfloor\frac{50}{25}\right\rfloor=10+2=12.

Cavab:

12

Məsələ 2.

100!

ədədinin sonunda neçə sıfır var?

Həll.

\mathrm{v}_5(100!)=20+4=24

. Cavab:

24

Məsələ 3.

2000!

ədədinin sonunda neçə sıfır var?

Həll.

\mathrm{v}_5(2000!)=400+80+16+3=499

. Cavab:

499

Məsələ 4.

100!

ədədini bölən

2

-nin ən böyük qüvvətini tapın.

Həll.

\mathrm{v}_2(100!)=50+25+12+6+3+1=97

. Yoxlama:

100=(1100100)_2

\mathrm{S}_2(100)=3

\dfrac{100-3}{1}=97

. Cavab:

2^{97}

Məsələ 5.

500!

ədədini bölən

7

-nin ən böyük qüvvətini tapın.

Həll.

\mathrm{v}_7(500!)=71+10+1=82

. Cavab:

7^{82}

Məsələ 6.

1000!

ədədini bölən

11

-in ən böyük qüvvətini tapın.

Həll.

\lfloor 1000/11\rfloor=90

\lfloor 1000/121\rfloor=8

\lfloor 1000/1331\rfloor=0

. Cəmi

98

. Cavab:

11^{98}

Məsələ 7.

100!

ədədini bölən

15

-in ən böyük qüvvətini tapın.

Həll.

15=3\cdot 5

, deməli

\mathrm{v}_{15}=\min\{\mathrm{v}_3(100!),\mathrm{v}_5(100!)\}=\min\{48,24\}=24

. Cavab:

15^{24}

Məsələ 8.

50!

ədədini bölən

6

-nın ən böyük qüvvətini tapın.

Həll.

\mathrm{v}_2(50!)=25+12+6+3+1=47

\mathrm{v}_3(50!)=16+5+1=22

. Minimum

22

. Cavab:

6^{22}

Məsələ 9.

100!

ədədini bölən

12

-nin ən böyük qüvvətini tapın.

Həll.

12=2^{2}\cdot 3

12^{k}\mid 100!

şərti

2k\le \mathrm{v}_2=97

və

k\le \mathrm{v}_3=48

deməkdir, yəni

k\le \min\{48,48\}=48

. Cavab:

12^{48}

Məsələ 10.

n!

ədədinin sonunda düz

1

sıfır olan bütün

n

-ləri tapın.

Həll.

\mathrm{v}_5(n!)=1

şərti

5\le n\le 9

verir (

n=10

-da artıq

2

olur). Cavab:

n\in\{5,6,7,8,9\}

Məsələ 11. Sonunda düz

5

sıfır olan

n!

varmı?

Həll.

\mathrm{v}_5(24!)=4

\mathrm{v}_5(25!)=5+1=6

. Yəni funksiya

4

-dən birbaşa

6

-ya sıçrayır —

5

qiyməti alınmır. Cavab: Yoxdur

Məsələ 12.

n!

ədədinin

10^{10}

-a bölündüyü ən kiçik

n

-i tapın.

Həll. Şərt

\mathrm{v}_5(n!)\ge 10

-dur (

\mathrm{v}_2

həmişə daha böyükdür).

\mathrm{v}_5(44!)=8+1=9

\mathrm{v}_5(45!)=9+1=10

. Cavab:

n=45

Məsələ 13.

2^{100}

ədədinin rəqəmlər cəminin

9

-a bölünməsindən alınan qalığı tapın.

Həll.

\mathrm{S}(N)\equiv N \pmod 9

2^{100} \bmod 9

2

-nin dövrü

6

-dır (

2,4,8,7,5,1

100=6\cdot16+4

, deməli

2^{100}\equiv 2^{4}=16\equiv 7

. Cavab:

7

Məsələ 14.

3^{2026}

ədədinin son rəqəmini tapın.

Həll.

3

-ün son rəqəmlərinin dövrü

3,9,7,1

— uzunluq

4

2026=4\cdot506+2

, deməli son rəqəm ikinci:

9

. Cavab:

9

Məsələ 15.

2^{2026}

ədədinin son iki rəqəmini tapın.

Həll.

\bmod\ 4

2^{2026}\equiv 0

\bmod\ 25

\varphi(25)=20

2026=20\cdot101+6

, deməli

2^{2026}\equiv 2^{6}=64\equiv 14

. ÇQT:

x\equiv 0\pmod4

x\equiv 14\pmod{25}

\Rightarrow

x=64

. Cavab:

64

Məsələ 16.

\underbrace{11\ldots1}_{2026}

ədədinin

9

-a bölünməsindən alınan qalığı tapın.

Həll. Rəqəmlər cəmi

2026

-dır və

2026\equiv 2+0+2+6=10\equiv 1 \pmod 9

. Cavab:

1

Məsələ 17.

2^{1000}

ədədində neçə rəqəm var? (

\log_{10}2=0{,}30103

)

Həll.

\lfloor 1000\cdot 0{,}30103\rfloor+1=\lfloor 301{,}03\rfloor+1=302

. Cavab:

302

Məsələ 18.

\dbinom{100}{50}

ədədini bölən

2

-nin ən böyük qüvvətini tapın.

Həll. Kummer (və ya mərkəzi binomial düsturu):

\mathrm{v}_2\binom{2n}{n}=\mathrm{S}_2(n)

. Burada

n=50=(110010)_2

, vahidlərin sayı

3

. Cavab:

2^{3}

8Orta və çətin məsələlər

Məsələ 19. Sonunda düz

2015

sıfır olan

n!

varmı?

Həll.

f(n)=\mathrm{v}_5(n!)

olsun;

f(n)\approx n/4

, deməli

n\approx 8060

ətrafına baxaq:

f(8055)=1611+322+64+12+2=2011,\quad f(8060)=1612+322+64+12+2=2012,

f(8065)=1613+322+64+12+2=2013,\quad f(8070)=1614+322+64+12+2=2014,

f(8075)=1615+323+64+12+2=2016.

Sonuncu addımda

8075=5^{2}\cdot 17\cdot 19

olduğundan

\lfloor n/25\rfloor

də sıçradı və

f

birbaşa

2014

-dən

2016

-ya keçdi. Deməli

2015

qiyməti alınmır. Cavab: Yoxdur

Məsələ 20. Sonunda düz

2026

sıfır olan bütün

n!

-ləri tapın.

Həll.

f(8115)=1623+324+64+12+2=2025

f(8120)=1624+324+64+12+2=2026

. Növbəti sıçrayış

n=8125=5^{4}\cdot 13

-dədir və orada

\mathrm{v}_5(8125)=4

olduğuna görə

f

birdən

4

artır (

2026\to 2030

). Deməli

f(n)=2026

olan

n

-lər

8120,\dots,8124

-dür. Cavab:

n\in\{8120,8121,8122,8123,8124\}

Məsələ 21.

n^{2}\nmid n!

olan bütün müsbət tam

n

-ləri tapın.

Həll. Uğursuz hallar.

n=p

sadə olarsa,

\mathrm{v}_p(p!)=1<2=\mathrm{v}_p(p^{2})

, deməli

p^{2}\nmid p!

n=4

üçün

16\nmid 24

. Qalan hallar bölünür.

n=1

aydındır. İndi

n

tərkib və

n\ne 4

olsun. İki hala ayıraq. Hal 1: $n=ab$ , burada $1<a<b<n$ . Onda

a

b

və

n

ədədləri

1,2,\dots,n

siyahısında fərqli elementlərdir, deməli onların hasili

n!

-i bölür:

a\cdot b\cdot n=n\cdot n=n^{2}\ \Big|\ n!.

Hal 2: belə ayrılış yoxdur. Bu, yalnız

n=p^{2}

(

p

sadə) olduqda baş verir. Onda

\mathrm{v}_p(n!)=\mathrm{v}_p\big((p^{2})!\big)=\left\lfloor\frac{p^{2}}{p}\right\rfloor+\left\lfloor\frac{p^{2}}{p^{2}}\right\rfloor=p+1,

bizə isə

\mathrm{v}_p(n^{2})=\mathrm{v}_p(p^{4})=4

lazımdır.

p\ge 3

üçün

p+1\ge 4

— bölünür.

p=2

üçün isə

p+1=3<4

— məhz

n=4

istisnası buradan gəlir. Cavab:

n=4

və bütün sadə ədədlər

Məsələ 22.

n!\cdot (n+1)!=m!

bərabərliyini ödəyən bütün müsbət tam

(n,m)

cütlərini tapın (

n\ge 1

Həll. Kiçik hallar:

n=1

1\cdot 2=2=2!

, yəni

m=2

n=6

6!\cdot 7!=720\cdot 5040=3\,628\,800=10!

, yəni

m=10

. Bu, məşhur

6!\cdot 7!=10!

eyniliyidir: doğrudan da

10!=10\cdot 9\cdot 8\cdot 7!=720\cdot 7!=6!\cdot 7!

. Cavab:

(n,m)=(1,2)

və

(6,10)

Məsələ 23.

1!+2!+\cdots+n!

cəminin son rəqəmini bütün

n\ge 4

üçün tapın.

Həll.

k\ge 5

üçün

10\mid k!

, deməli cəmin son rəqəmi

1!+2!+3!+4!=33

-ün son rəqəmi ilə eynidir. Cavab:

3

Məsələ 24.

1!+2!+\cdots+n!

cəminin

27

-yə bölündüyü bütün

n

qiymətlərini tapın.

Həll.

T_n

ilə cəmi işarə edək.

k\ge 9

üçün

\mathrm{v}_3(k!)\ge 4

, deməli

27\mid k!

. Odur ki

n\ge 8

üçün

T_n\equiv T_8 \pmod{27}

. Hesablayaq:

T_1=1

T_2=3

T_3=9

T_4=33

T_5=153

T_6=873

T_7=5913

T_8=46233

. Mod

27

1,3,9,6,18,9,0,9

. Deməli yalnız

n=7

üçün

27\mid T_n

, və

n\ge 8

üçün qalıq həmişə

9

-dur. Cavab: Yalnız

n=7

Məsələ 25.

\dbinom{2n}{n}

ədədinin

2

-nin qüvvəti olduğu bütün

n\ge 1

qiymətlərini tapın.

Həll.

n=1

\binom21=2=2^{1}

(bəli).

n=2

\binom42=6

— yox.

n=3

20

— yox.

n=4

70

— yox. Ümumi halda Bertran postulatı ilə

n<p\le 2n

olan

p

sadə ədədi var. Onda

p

ədədi

(2n)!

-i bölür (çünki

p\le 2n

), lakin

n!

-i bölmür (çünki

p>n

). Kummer və ya birbaşa Legendre ilə

\mathrm{v}_p\binom{2n}{n}=\left\lfloor\frac{2n}{p}\right\rfloor-2\left\lfloor\frac{n}{p}\right\rfloor=1-0=1,

deməli

\binom{2n}{n}

tək sadə ədəd

p

-yə bölünür və

2

-nin qüvvəti ola bilməz — bir şərtlə ki,

p\ne 2

n\ge 2

üçün

p>n\ge 2

, yəni

p

tək sadədir. Cavab: Yalnız

n=1

Məsələ 26.

n!

ifadəsinin tam kub olduğu bütün

n\ge 1

qiymətlərini tapın.

Həll.

n=1

1=1^{3}

(bəli).

n=2

2

;

n=3

6

— kub deyil.

n\ge 4

olsun. Bertran postulatına görə

n/2<p\le n

şərtini ödəyən

p

sadə ədədi var. Onda

2p>n

olduğundan

1,\dots,n

arasında

p

-nin yeganə qatı

p

-nin özüdür; həmçinin

p>n/2\ge 2

və

n\ge 4

olduğundan

p^{2}>n^{2}/4\ge n

. Deməli Legendre cəmində yalnız bir həd qalır:

\mathrm{v}_p(n!)=\left\lfloor\frac{n}{p}\right\rfloor=1.

Tam kubda hər sadə ədədin göstəricisi

3

-ə bölünməlidir,

1

isə bölünmür — ziddiyyət. Cavab: Yalnız

n=1

Məsələ 27.

n!

ədədinin

2^{n}

-ə bölünmədiyini isbat edin (hər

n\ge 1

üçün), və

\mathrm{v}_2(n!)=n-1

olan bütün

n

-ləri tapın.

Həll. Rəqəmlər cəmi düsturu ilə

\mathrm{v}_2(n!)=n-\mathrm{S}_2(n)

\mathrm{S}_2(n)\ge 1

olduğundan

\mathrm{v}_2(n!)=n-\mathrm{S}_2(n)\le n-1<n,

yəni

2^{n}\nmid n!

. Bərabərlik

\mathrm{v}_2(n!)=n-1

məhz

\mathrm{S}_2(n)=1

olduqda, yəni

n

ikinin qüvvəti olduqda alınır. Cavab:

n=2^{k}

k\ge 0

Məsələ 28.

\mathrm{v}_3(n!)\ge 100

olan ən kiçik

n

-i tapın.

Həll.

\mathrm{v}_3(n!)=\dfrac{n-\mathrm{S}_3(n)}{2}\ge 100 \iff n-\mathrm{S}_3(n)\ge 200

n\approx 200

-dən başlayaq.

n=204

\lfloor 204/3\rfloor=68

\lfloor204/9\rfloor=22

\lfloor204/27\rfloor=7

\lfloor204/81\rfloor=2

, cəmi

99

n=205,206

: dəyişmir (

3\nmid 205,206

), yenə

99

n=207

69+23+7+2=101

. Deməli

\ge 100

ilk dəfə

n=207

-də alınır (və

100

qiyməti heç vaxt alınmır). Cavab:

n=207

Məsələ 29.

\dbinom{1000}{500}

ədədini bölən

5

-in ən böyük qüvvətini tapın.

Həll. Kummer:

500

-ü

5

əsasında yazaq.

500=4\cdot 125+0\cdot 25+0\cdot 5+0=(4000)_5

. Toplama

(4000)_5+(4000)_5

: sıfırıncı, birinci və ikinci sütunlarda

0+0=0

— keçid yox; üçüncü sütunda

4+4=8=1\cdot 5+3

— keçid var. Cəmi

1

keçid. Yoxlama:

\mathrm{v}_5(1000!)=200+40+8+1=249

\mathrm{v}_5(500!)=100+20+4+0=124

249-248=1

. Cavab:

5^{1}

Məsələ 30.

4444^{4444}

ədədinin rəqəmlər cəmi

B

B

-nin rəqəmlər cəmi

C

-dir.

C

-nin rəqəmlər cəmini tapın. (IMO 1975)

Həll. Bu, §4-dəki Nümunənin özüdür: sərhəd

\mathrm{S}(C)\le 12

verir, mod

9

invariantı isə

\mathrm{S}(C)\equiv 4444^{4444}\equiv 7

verir. Cavab:

7

Məsələ 31. Elə

n

müsbət tam ədədi varmı ki,

\mathrm{S}(n)=100

və

\mathrm{S}(n^{2})=10\,000

olsun?

Həll. Əvvəlcə invariantı yoxlayaq.

\mathrm{S}(n)=100\equiv 1 \pmod 9

, deməli

n\equiv 1

, buradan

n^{2}\equiv 1 \pmod 9

. Digər tərəfdən

\mathrm{S}(n^{2})=10\,000\equiv 1 \pmod 9

. Ziddiyyət yoxdur — deməli maneə axtarmaq yox, nümunə qurmaq lazımdır. Konstruksiya. Vahidləri o qədər seyrək düzək ki, kvadrata yüksəldərkən heç bir keçid baş verməsin:

n=\sum_{j=0}^{99}10^{\,2^{j}}.

Burada

\mathrm{S}(n)=100

(yüz dənə vahid, hamısı ayrı mövqedə). Kvadratı açaq:

n^{2}=\sum_{i=0}^{99}\sum_{j=0}^{99}10^{\,2^{i}+2^{j}}.

Göstəricilər arasında təkrarı öyrənək:

2^{i}+2^{j}=2^{k}+2^{\ell}

bərabərliyi ikilik yazılışın yeganəliyinə görə yalnız

\{i,j\}=\{k,\ell\}

olduqda mümkündür. Deməli:

• $i=j$ olan $100$ hədd bir-birindən fərqli göstəricilər verir və hər birinin əmsalı $1$ -dir;
• $i\ne j$ olan hədlər cüt-cüt birləşir ( $(i,j)$ və $(j,i)$ ), yəni $\binom{100}{2}=4950$ fərqli göstəricinin hər birində əmsal $2$ -dir.

Bütün əmsallar

1

və ya

2

olduğundan heç bir keçid yoxdur və rəqəmlər cəmi sadəcə əmsalların cəmidir:

\mathrm{S}\big(n^{2}\big)=100\cdot 1+4950\cdot 2=100+9900=10\,000.

Cavab: Bəli, məsələn

n=\sum_{j=0}^{99}10^{\,2^{j}}

Məsələ 32.

n!+5

ifadəsinin tam kvadrat olduğu bütün müsbət tam

n

-ləri tapın.

Həll. Kiçik hallar:

n=1

6

;

n=2

7

;

n=3

11

;

n=4

29

;

n=5

125

;

n=6

725

. Heç biri kvadrat deyil (

125

və

725

üçün:

11^{2}=121

12^{2}=144

;

26^{2}=676

27^{2}=729

n\ge 7

olsun. Onda

9\mid n!

(çünki

3

və

6

vuruqları var, hətta

n\ge 6

kifayətdir), deməli

n!+5\equiv 5 \pmod 9.

Tam kvadratlar mod

9

-da yalnız

0,1,4,7

qalıqlarını verir.

5

bu siyahıda yoxdur. Cavab: Həll yoxdur

Məsələ 33.

n!+2^{n}

ifadəsinin tam kvadrat olduğu bütün

n\le 12

qiymətlərini tapın.

Həll. Birbaşa yoxlayaq:

\begin{array}{c|cc} n & n!+2^{n} & \text{kvadrat?}\\\hline 1&3&-\\ 2&6&-\\ 3&14&-\\ 4&40&-\\ 5&152&-\\ 6&784=28^{2}&\text{bəli}\\ 7&5168&-\\ 8&40576&-\\ 9&363392&-\\ 10&3629824&-\\ 11&39918848&-\\ 12&479005696&- \end{array}

(

n=12

479005696=21886{,}2\ldots^{2}

deyil;

21886^{2}=478996996

21887^{2}=479040769

.) Cavab:

n=6

Məsələ 34.

100!

ədədinin sonundakı sıfırları atdıqdan sonra qalan ədədin son rəqəmini tapın.

Həll.

\mathrm{v}_5(100!)=24

\mathrm{v}_2(100!)=97

. Deməli

100!=10^{24}\cdot 2^{73}\cdot M

, burada

M=100!/(2^{97}5^{24})

ədədi

10

-a qarşılıqlı sadədir. Bizə

N=2^{73}M \bmod 10

lazımdır;

N

cütdür, ona görə mod

5

tapmaq kifayətdir.

100!/5^{24}

ifadəsini mod

5

hesablayaq. Vilson tipli qayda:

1,\dots,5k

arasında

5

-ə bölünməyənlərin hasili

\equiv (-1)^{k} \pmod 5

. Rekursiv olaraq

\frac{100!}{5^{24}}\equiv (-1)^{20}\cdot \frac{20!}{5^{4}}\equiv \frac{20!}{5^{4}},\qquad \frac{20!}{5^{4}}\equiv(-1)^{4}\cdot\frac{4!}{5^{0}}=24\equiv 4 \pmod 5.

Deməli

100!/5^{24}\equiv 4 \pmod 5

. İndi

2^{24}

-ə bölmək lazımdır:

2^{4}\equiv 1\pmod 5

24=4\cdot 6

, deməli

2^{24}\equiv 1

və

\frac{100!}{10^{24}}\equiv 4 \pmod 5.

Bu ədəd cütdür, mod

10

-da cüt olub mod

5

-də

4

verən yeganə qalıq

4

-dür. Cavab:

4

Məsələ 35.

\mathrm{S}(n)=\mathrm{S}(2n)

olan sonsuz sayda

n

olduğunu göstərin və belə hər

n

-in

9

-a bölündüyünü isbat edin.

Həll. Bölünmə.

\mathrm{S}(2n)\equiv 2n

və

\mathrm{S}(n)\equiv n \pmod 9

. Bərabərlikdən

2n\equiv n \pmod 9

, yəni

9\mid n

. Sonsuzluq.

n_k=\underbrace{9\ldots9}_{k}=10^{k}-1

götürək. Onda

\mathrm{S}(n_k)=9k

və

2n_k=2\cdot 10^{k}-2=1\underbrace{9\ldots9}_{k-1}8,

buradan

\mathrm{S}(2n_k)=1+9(k-1)+8=9k

. Deməli hər

k\ge 1

üçün

\mathrm{S}(n_k)=\mathrm{S}(2n_k)

. Cavab: Məsələn

n=\underbrace{9\ldots9}_{k}

, hər

k\ge 1

üçün

Məsələ 36.

1000!

ədədinin onluq yazılışında neçə rəqəm var? (

\log_{10}

cədvəlindən istifadə edərək qiymətləndirin; dəqiq cavab

2568

-dir.) Stirlinq yaxınlaşmasından istifadə etmədən yalnız

\log_{10}(1000!)=\sum_{k=1}^{1000}\log_{10}k

olduğunu əsaslandırın.

Həll. Rəqəmlərin sayı

\lfloor \log_{10}(1000!)\rfloor+1

-dir. Loqarifmin əsas xassəsinə görə

\log_{10}(1000!)=\log_{10}\big(1\cdot 2\cdots 1000\big)=\sum_{k=1}^{1000}\log_{10}k.

Bu cəmin qiyməti

2567{,}6\ldots

-dır, deməli rəqəmlərin sayı

2568

-dir. Kobud yoxlama.

1000!<1000^{1000}=10^{3000}

və

1000!>500^{500}=10^{500\log_{10}500}\approx 10^{1349}

, yəni rəqəm sayı

1350

ilə

3000

arasındadır —

2568

bu aralığa düşür. Cavab:

2568

Məsələ 37.

n

və

n^{2}

ədədlərinin onluq yazılışında bütün rəqəmlər eynidirsə (yəni

n^{2}

-nin rəqəmləri

n

-in rəqəmlərinin bir yerdəyişməsidirsə),

9\mid n-1

və ya

9 \mid n

olduğunu isbat edin.

Həll. Rəqəmlər eyni olduğundan

\mathrm{S}(n^{2})=\mathrm{S}(n)

. Mod

9

-da

n^{2}\equiv \mathrm{S}(n^{2})=\mathrm{S}(n)\equiv n \pmod 9\ \Longrightarrow\ 9\mid n^{2}-n=n(n-1).

\mbox{ƏBOB}(n,n-1)=1

olduğundan

9

-un

3

-lük vuruqları eyni ədədə düşməlidir: ya

9\mid n

, ya da

9\mid n-1

Məsələ 38.

p

sadə ədəddir.

\dbinom{2p}{p}-2

ifadəsinin

p^{3}

-ə bölündüyünü isbat edin (

p\ge 5

). (Wolstenholme nəticəsi)

Həll. Əvvəlcə bir xəbərdarlıq:

p\ge 3

üçün

\mathrm{v}_p\binom{2p}{p}=\mathbf{0}

-dır, yəni

\binom{2p}{p}

ədədi

p

-yə bölünmür. Doğrudan da, Kummer teoreminə görə

p+p

toplamasını

p

əsasında aparaq:

p=(10)_p

və

(10)_p+(10)_p=(20)_p

;

p\ge 3

olduğuna görə

2<p

, deməli heç bir sütunda keçid baş vermir. (Bu, iddianın özü üçün də zəruridir:

p\mid \binom{2p}{p}

olsaydı,

\binom{2p}{p}-2

ədədi

p

-yə bölünə bilməzdi.) Yoxlama:

\binom{10}{5}=252

və

5\nmid 252

; həqiqətən

252-2=250=2\cdot 5^{3}

.İndi isə əsas addım:

\binom{2p}{p}=\frac{(2p)!}{p!\,p!}=2\cdot\frac{(2p-1)!}{p!\,(p-1)!}=2\binom{2p-1}{p-1}.

Deməli iddia

\binom{2p-1}{p-1}\equiv 1 \pmod{p^{3}}

şəklinə düşür — bu, Wolstenholme teoremidir. İsbatın özəyi:

\binom{2p-1}{p-1}=\prod_{k=1}^{p-1}\frac{p+k}{k}=\prod_{k=1}^{p-1}\left(1+\frac{p}{k}\right) =1+p\sum_{k=1}^{p-1}\frac1k+p^{2}\!\!\sum_{1\le i<j\le p-1}\!\!\frac{1}{ij}+\cdots

Burada

\sum_{k=1}^{p-1}\frac1k\equiv 0 \pmod{p^{2}}

(Wolstenholme-un birinci hissəsi:

\frac1k

ilə

\frac{1}{p-k}

cütləşdirilir) və

\sum_{i<j}\frac{1}{ij}\equiv 0\pmod p

olduğu göstərilir. Nəticədə bütün düzəliş hədləri

p^{3}

-ə bölünür. Zəif, lakin olimpiada üçün adətən kifayət edən variant:

\binom{2p}{p}\equiv 2 \pmod{p^{2}}

. Bunun üçün yuxarıdakı hasildə yalnız birinci dərəcəli həddə qədər açmaq və

\sum_{k=1}^{p-1}\frac1k\equiv 0\pmod p

olduğunu (cütləşdirmə ilə) göstərmək kifayətdir.