Глава 1

Делимости. Сравнения. Функция на Ойлер.


страницата се нуждае от дописване/преглеждане


В началото на този курс ще вземем малко теория на числата - делимости, сравнения, функция на Ойлер итн. След това продължаваме с по-сериозните неща :)

Делимости

Дефиниция: Нека $a, b \in \mathbb Z$.
Казваме, че $a$ дели $b$ и записваме $a / b$, ако $\exists k \in \mathbb Z$, такова че $b = ak$.
Свойства:

  • $a / a$ - рефлексивност
  • $a / b \And b / a \Rightarrow a = \pm b$
  • $a / b \And b / c \Rightarrow a / c$ - транзитивност
  • $a / b \And a / c \Rightarrow a / \lambda b + \mu c \quad \lambda, \mu \in \mathbb Z$

Алгоритъм на Евклид

Това е може би първият и най-известен алгоритъм въобще! Използва се за намиране на НОД (Най-голям Общ Делител). Първо да си припомним какво беше това:

Дефиниция: Нека $a, b \in \mathbb Z$. Казваме, че $d$ е НОД на $a$ и $b$ и записваме $d = (a, b)$, ако:

  • $d > 0$;
  • $d / a \And d / b$ - т.е $d$ се явява общ делител на $a$ и $b$;
  • $d' / a \And d' / b \Rightarrow d' / d$ - всеки друг общ делител го дели.

Алгоритъма на Евклид: Идеята е много проста - ще делим голямото на малкото число, и после повтаряме операцията за малкото и остатъка, докато остатъка не стане 0:
Пример: Да намерим $(102, 94)$.

(1)
\begin{eqnarray} 102 &=& 94 * 1 + 8 \\ 94 &=& 8*11 + 6 \\ 8 &=& 6*1 + 2 \\ 6 &=& 2*3 + 0 \end{eqnarray}

Стигнахме до остатък 0 - следователно последния остатък е търсения НОД - т.е 2.

Теорема на Безу

Най-големият общ делител е много важна концепция, но в почти всички реални приложения се налага да се изкопче и още малко информация относно числата и него - на помощ идва теоремата на Безу:

Теорема: Ако $d = (a, b)$, тогава съществуват $u, v \in \mathbb Z$, такива че $d = au + bv$.
Пример: Как точно да намираме числата? Ами това става с тъй-наречения разширен алгоритъм на Евклид, но в общи линии идеята е да се върнем назад по сметките на Евклид и постепенно да строим $u, v$:

(2)
\begin{eqnarray} 2 &=& 8 - 6*1\\ &=& 8 - (94 - 8 * 11) * 1 \\ &=& -94 - 8 * 12 \\ &=& -94 + (102 - 94) * 12 \\ &=& = 94 * (-13) + 102 * 12 \end{eqnarray}

Теорема 1: $a / bc \And (a, b) = 1 \Rightarrow a / c$
Теорема 2: $a / b \And b / c \And (a, b) = 1 \Rightarrow ab / c$
Дефиниция: $p > 1 \And p \in \mathbb N$. Ще казваме, че $p$ е просто, ако единствените му делители са $\pm 1, \pm p$.
Теорема(Основна Теорема на Алгебрата - ОТА): Нека $n \in \mathbb N, n > 1$. Тогава съществува единствено разлагане на $n$ във произведение на прости множители по следния начин:

(3)
\begin{align} n = p_1^{k_1} p_2^{k_2} \cdots p_s^{k_s} \end{align}

Където $p_i$ са прости числа, а $k_i$ са естествени числа.

Задачи

Задача 1

Да се докаже, че $\forall m \in \mathbb N$ е изпълнено $30 / m^5 - m$

Решение: Първо ще разложим израза $m^5 - m$ за по-удобно:

(4)
\begin{equation} A = m^5 - m = m(m^4 - 1) = m(m^2+1)(m^2-1) = m(m^2+1)(m+1)(m-1) \end{equation}

Ще използваме двукратно втората теорема и разлагането на 30 на прости множители: $30 = 2.3.5$
1) $2 / A$. Очевидно в разлагането на $A$ участват 2 последователни числа : $m$ и $m+1$. Ако разгледаме случаи за това какъв остатък дава $m$ при деление на 2 ще се уверим, че произведението им винаги се дели на 2, и следователно $2 / A$
2) $3 / A$. Аналогично на горния случай имаме 3 последователни числа : $m-1, m, m+1$. Разглеждаме случай за това какъв остатък дава $m$ при деление на 3 и получаваме, че при всички случаи се дели на 3 - т.е получихме, че $3 / A$
3) $5 / A$. Тук вече ще трябва найстина да разгледаме няколко случая:

  • $m = 5k$. От тук веднага получаваме, че $5 / m$ а следователно и $5 / A$;
  • $m = 5k\pm 1$. Сега пък имаме, че $5 / (m-1)(m+1) = m^2 - 1$, от където и $5 / A$;
  • $m = 5k \pm 2$. В този случай имаме, че $5 / m^2 + 1$, следователно $5 / A$.

Окончателно получихме, че и $5 / A$ (от 3те подслучая) и прилагайки двукратно Теорема 2 от точки 1) 2) 3) получаваме $30 / A$.

Задача 2

Да се докаже, че $\nexists n, m \in \mathbb N$, такива че $(2n)^{2n} - 1 = m^3$.

Решение: Да допуснем че съществуват. Нека положим $A = (2n)^{2n} - 1$ и да го разложим:

(5)
\begin{align} A = (2n)^{2n} - 1 = \underbrace{((2n)^{n} - 1)}_{B}\underbrace{((2n)^n + 1)}_{C} \end{align}

Ще докажем, че $(B, C) = 1$. Ами очевидно $C - B = 2$ и следователно единствените възможни делители на $B, C$ са само $\{ \pm 1, \pm 2 \}$. Обаче $\pm 2$ очевидно не са делители, защото и двете числа са нечетни. Т.е остана само $1$.
Понеже $A \ge 3$, то $m$ е поне 2. Прилагаме ОТА за $m$ и получаваме: $\exists p_1, p_2, \cdots, p_s \And k_1,k_2, \cdots, k_s$ такива че $m = p_1^{k_1} p_2 ^{k_2} \cdots p_s^{k_s}$. От където имаме:

(6)
\begin{align} BC = m^3 = p_1^{3k_1} p_2 ^{3k_2} \cdots p_s^{3k_s} \end{align}

Тъй като $(B, C) = 1$, то ако едно просто число дели едното от тях, то със сигурност не дели другото - т.е едно просто число или 'влиза' с цялата си степен в $B$ или с цялата си степен в $C$. Така получихме, че всички прости числа участващи в разлагането на $B, C$ са на степени, кратни на 3. От тук тривиално имаме $B = b^3 \And C = c^3$. Да разпишем отново $C - B$:

(7)
\begin{align} 2 = C - B = c^3 - b^3 = \underbrace{(c-b)}_{\ge 1}\underbrace{(c^2 + cb + b^2)}_{\ge 3} \ge 3 \end{align}

С което стигнахме до противоречие! Допуснатото е невярно - следователно не съществуват $n, m$ за който $(2n)^{2n} - 1 = m^3$.

Задача 3

Да се докаже, че числото $A_n = (n+1)(n+2)\cdots(n+n)$ се дели на $2^n$, но не се дели на $2^{n+1}$.

Доказателство:
Ще направим доказателство по индукция.
База: При $n = 1$ $2^1 / (1+1)$ и $2^2 \nmid (1+1)$ - ок
Индукционна хипотеза: Допускаме, че е изпълнено за $n$ - т.е $2^n / A_n \And 2^{n+1} \nmid A_n$
Индукционна стъпка:

(8)
\begin{eqnarray} A_{n+1} &=& ((n+1) + 1)((n+1)+2)\cdots((n+1) + n)((n+1)+(n+1)) \\ &=& (n+2)(n+3)\cdots(n+n)(n+n+1)(2(n+1)) \\ &=& 2 (n+1)(n+2)\cdots(n+n)(n+n+1) \\ &=& 2 A_n (n+n+1) \\ \end{eqnarray}

От индукционното предположение получаваме, че $2^n / A_n$ следователно $2^{n+1} / 2A_n(n+n+1) = A_{n+1}$. От друга страна ако допуснем, че $2^{n+2}$ дели $A_{n+1}$, тъй като $(2^{n+2}, (n+n+1)) = 1$ получаваме, че $2^{n+2} / 2A_n$ от където $2^{n+1} / A_n$ - противоречие (от индукционното предположение).

Задача 4

Да се намери броя на рационалните числа в интервала $[0, 1]$, такива че предстаени във вид на непрекъсната дроб $\frac{p}{q}$ е изпълнено $pq = 20!$.

Решение: Първо ще проверим, кои са простите делители на $20!$. Тривиално се вижда, че това са $2, 3, 5, 7, 11, 13, 17, 19$. Степените, на които участват не са от значение. Тъй като несъкратимите дроби имат взаимно прост числител и знаменател, то ако примерно $2$ дели $p$ със сигурност $2 \nmid q$, т.е $2$ участва на максимална степен в $p$ (всички множители $2$ са във $p$). Прилагайки същото разсъждение за всички делители получаваме, че числителя и знаменателя са фиксирани с точност до това, кой делители участват в числителя (другите ще участват съответно в знаменателя). Сега остава да видим, че от всички възможни дроби, чиито произведение на числителя и знаменателя е $20!$ точно половината са в интервала $[0, 1]$. Така окончателно получихме $\frac{2^8}{2} = 2^7$ числа с исканото свойство ($2^8$ начина да се избере произволно подмножество от 8те делителя и взимаме само половината, защото другите са $> 1$).

Сравнения

Дефиниция: Нека $a, b \in \mathbb Z$ и $m \in \mathbb N$. Казваме, че $a$ е сравнимо с $b$ по модул $m$ (записваме $a \equiv b \pmod{m}$), ако $m / a - b$.

Свойства:

  • $a \equiv a \pmod{m}$ - рефлексивна
  • $a \equiv b \pmod m \Rightarrow b \equiv a \pmod m$ - симетрична
  • $a \equiv b \pmod m \And b \equiv c \pmod m \Rightarrow a \equiv c \pmod m$ - транзитивна
  • $a_1 \equiv b_1 \pmod m \And a_2 \equiv b_2 \pmod m \Rightarrow a_1 + a_2 \equiv b_1 + b_2 \pmod m \And a_1a_2 \equiv b_1b_2 \pmod m$
  • $a_1 \equiv b_1 \pmod m \Rightarrow a_1^k \equiv b_1^k \pmod m \quad \forall k \in \mathbb N \cup \{ 0 \}$

Доказателство на $a_1a_2 \equiv b_1b_2 \pmod m$.

(9)
\begin{eqnarray} \left{}\begin{array}{rcl} a_1 \equiv b_1 \pmod m &\Rightarrow& m / a_1 - b_1 \\ a_2 \equiv b_2 \pmod m &\Rightarrow& m / a_2 - b_2 \\ \end{array}\right\} \Rightarrow m &/& a_1 (a_2 - b_2) + b_2(a_1 - b_1) \\ &=& a_1a_2 - a_1b_2 + a_1b_2 - b_1b_2\\ &=& a_1a_2 - b_1b_2 \\ &\Rightarrow& a_1a_2 \equiv b_1b_2 \pmod m \end{eqnarray}

Тези свойства ни позволяват да образуваме групи според остатъците при деление на някакво число.

Алгоритъм на Ойлер (за решаване на уравнения със сравнения)

Искаме да решим $11x \equiv 7 \pmod{15}$.
Тогава съществува $y \in \mathbb Z$, за което $11x - 7 = 15y$.
Изразяваме променливата, пред която има по-малък коефициент (в случая $x$):

(10)
\begin{align} x = \frac{15y + 7}{11} = y + \underbrace{\frac{4y+7}{11}}_{u} \quad u \in \mathbb Z \end{align}

T.е съществува $u \in \mathbb Z$, за което $11u = 4y + 7$.
Отново изразяваме променливата, пред която има по-малък коефициент (в случая $y$):

(11)
\begin{align} y = \frac{11u-7}{4} = \frac{(12-1)u - 7}{4} = 3u-\underbrace{\frac{u+7}{4}}_{v} \quad v \in \mathbb Z \end{align}

Т.е съществува $v \in \mathbb Z$, за което $u = 4v - 7$.
Получихме формула за $u$, съответно и за $y$ и $x$, за които $x$ е цяло. Просто трябва да се върнем назад:

(12)
\begin{eqnarray} y &=& \frac{11u - 7}{4} = \frac{11(4v - 7)-7}{4} = 11v - 21 \\ x &=& \frac{15y+7}{11} = 15v-28 \equiv 2 \pmod{15} \\ \end{eqnarray}

Т.е окончателно получихме, че $x \equiv 2 \pmod{15}$, т.е решихме модулното уравнение.

Задача 5

Да се намерят всички прости числа $p$, за които $p + 10$ и $p + 20$ също са прости.

Решение: Очевидно $3$ върши работа.
Сега ще докажем, че няма по-големи. Нека $p$ е просто и $p > 3$, тогава $p = 3k+1$ или $p=3k+2$.

  • $p = 3k + 1$, тогава $p+20 = 3k+1 + 20 = 3k+21$, което се дели на 3 и е по-голямо от 3, следователно не е просто!
  • $p = 3k + 2$, тогава $p+10 = 3k+2+10 = 3k+12$, което се дели на 3 и е по-голямо от 3, следователно не е просто!

Т.е остава само $p = 3$.

Функция на Ойлер

Дефиниция: Функцията на Ойлер $\varphi : \mathbb N \to \mathbb N$, е такава че $\varphi(n) = | \{ x | (x, n) = 1 \And x < n \} |$, т.е броя на числата по-малки от $n$, които са взаимно прости с $n$.
Свойства:

  • $\varphi(p) = p - 1$ при $p$ просто;
  • $\varphi(p^n) = p^{n-1}(p-1) = p^n(1-\frac{1}{p})$ при $p$ просто;
  • $\varphi(ab) = \varphi(a)\varphi(b)$ ако $(a, b) = 1$.

Задача 6

Да се намери броят на естествените числа $< 2009$, които се делят на $3$ и $7$, но не се делят на $2$ и на $9$.

Решение:

$1v$ $1 \le v \le 2008$ $1, 2, 3, \cdots, 2008$ всички числа
$3k$ $1 \le k \le \left \lfloor \frac{2008}{3} \right \rfloor = 669$ $3, 6, 9, \cdots, 2007$ делящите се на $3$
$3.7p$ $1 \le p \le \left \lfloor \frac{669}{7} \right \rfloor = 95$ $21, 42, 63, \cdots, 1995$ делящи се на $3$ и $7$
$3.7(2t + 1)$ $0 \le t \le \left \lfloor \frac{95-1}{2} \right \rfloor = 47$ $21, 63, \cdots, 1995$ делящи се на $3$ и $7$, но неделящи се на $2$
$3.7(2(3s+1\pm 1)+1)$ $0 \le s \le \left \lfloor \frac{47}{3} \right \rfloor = 15$ $2, 3, 5, 6, \cdots, 44, 45, 47$ делящи се на $3$ и $7$, но неделящи се на $2$ и $9$

окончателно получихме $2.15 = 30$ числа.

Теорема на Ферма-Ойлер

Нека $a \in \mathbb Z$ и $m \in \mathbb N$ и $(a, m) = 1$. Тогава $a^{\varphi(m)} \equiv 1 \pmod m$.

Следствие(теоремата на Ферма): Ако $a \in \mathbb Z$, и $m$ е просто, то $a^{p-1} \equiv 1 \pmod m$.

Задача 8

Да се намерят последните 2 цифри на числото $137^42$.
Решение: Намирането на последните две цифри е всъщност намирането на остатъка при деление със $100$.
Тъй като $(137, 100) = 1$, то по ТФО имаме $137^{\varphi(100)} \equiv 1 \pmod{100}$.
Използваме, че $\varphi(100) = \varphi(2^2.5^2) = \varphi(2^2) \varphi(5^2) = 2(2-1)5(5-1) = 2.5.4 = 40$, т.е $137^{40} \equiv 1 \pmod{100}$
Остава да ползваме $137^2 \equiv 69 \pmod{100}$, и като умножим 2те сравнения получаваме $137^{42} \equiv 69 \pmod{100}$

Задача 9

Да се намери остатъка при деление на $2^{1000} + 3^{1000}$ с $18$.

Решение: Нека $A = 2^{1000} + 3^{1000}$.

1ви начин:

(13)
\begin{eqnarray} 1 &=& 1^{1000} \\ &=& (3-2)^{1000} \\ &=& 3^{1000} \underbrace{- \binom{1000}{1}3^{999}.2 + \binom{1000}{2}3^{998}.2^2 - \cdots + \binom{1000}{998} 3^2 2^{998}}_{18k} - \binom{1000}{999}3^1.2^{999} + 2^{1000} \\ &=& A+18k-3.2^{999} . 1000 \end{eqnarray}

Т.е получихме, че $A \equiv 3.2^{999}.1000 + 1 \pmod{18}$.
$3000 \equiv 12 \pmod{18}$.
Ще разгледаме остатъка при деление на $2^{999}$ с $9$, защото са взаимно прости (и може да ползваме ТФО).
Имаме $2^{\varphi(9)} = 2^6 \equiv 1 \pmod 9 \Rightarrow 2^{996} \equiv 1 \pmod 9$. От друга страна $2^3 \equiv 8 \pmod 9$, т.е окончателно $2^{999} \equiv 8 \pmod 9$, което е равносилно на $9 / 2^{999} - 8$. Използваме, че $2 / 2^{999} - 8$ и разбира се $(2, 9) = 1$, за да получим $18 / 2^{999} - 8$, от където $2^{999} \equiv 8 \pmod{18}$.
Сега вече $A \equiv 3000.2^{999} + 1 \equiv 8.12 + 1 \equiv 7 \pmod{18}$.

2ри начин:
Тъй като понякога може да се случи числата да не са толкова приятни, ето и още един начин за решаване на задачата:
Идея: намираме остатъка на $2^{1000}$ по модул $18$ и остатъка на $3^{1000}$ по модул $18$, събираме ги и воала!

Нека започнем като ученици:

$2^1 \equiv 2 \pmod {18}$
$2^2 \equiv 4 \pmod {18}$
$2^3 \equiv 8 \pmod {18}$
$2^4 \equiv 16 \pmod {18}$
$2^5 \equiv 14 \pmod {18}$
$2^6 \equiv 10 \pmod {18 }$
$2^7 \equiv 2 \pmod {18}$

Супер, получихме, че $2^1$ и $2^7$ дават един и същи остатък при деление на $18$.
Това значи, че остатъците почват да се повтарят и на която и степен да повдигнен двойката, ще получим един от първите шест остатъка.
Чудесно! А сега нека сметнем, че $1000 = 166*6 + 4$ (деление с частно и остатък).
Твърдя, че $2^{1000}$ и $2^4$ дават един и същи остатък при деление с $18$, тъй като $1000$ и $4$ дават един и същи остатък при деление с $6$.
От тук следва, че $2^{1000} \equiv 16 \pmod {18}$ (1)

За $3^{1000}$ е дори още по-лесно:
$3^1 \equiv 3 \pmod {18}$
$3^2 \equiv 9 \pmod {18}$
$3^3 \equiv 9 \pmod {18}$
$3^4 \equiv 9 \pmod {18}$
$\vdots$
$3^{1000} \equiv 9 \pmod {18}$ (2)

/*За по-педантичните - проведете пълната индукция и си докажете, че $3^n \equiv 9 \pmod {18}, \quad n > 1$.
Аз лично говорих с ас. Е. Михайлова и тя каза, че е достатъчно само да се покаже реда на остатъците.
Разбира се, никой няма да е ощетен, ако го докаже. */

От (1) и (2) следва, че $2^{1000} + 3^{1000} \equiv 16+9 \pmod {18}$, т.е. $A \equiv 7 \pmod {18}$.

Задача 10

Да се реши системата сравнения:

(14)
\begin{array} {|rcl} 3x &\equiv& 1 \pmod 7 \\ 4x &\equiv& 5 \pmod{11} \\ 2x &\equiv& 3 \pmod 5 \\ \end{array}

Решение: Задачата има много решения. Тук ще илюстрирам само едно (ако някой желае - да напише още).
Идея: Вече знаем да решаваме сравнения по метода на Ойлер. Ще решим всяко едно сравнение и накрая ще обединим резултатите. Интересното в случая е че обединяването на резултатите всъщност е пак решаване на сравнение.

Няма да пиша индивидуалното решаване на всяко от сравненията - всеки може да си ги сметне сам. Стигаме до:

(15)
\begin{array} {|rcl} x &\equiv& 5 \pmod 7\\ x &\equiv& 4 \pmod{11}\\ x &\equiv& 4 \pmod 5 \end{array}

Ще си посъкратим малко работата като обединим първо последните 2 сравнения:

(16)
\begin{align} \begin{array}{|rcl} x &\equiv& 4 \pmod{11}\\ x &\equiv& 4 \pmod 5 \end{array} \iff \begin{array}{|rcl} 11 &/& x - 4\\ 5 &/& x - 4 \end{array} \overset{\underset{(11, 5) = 1}{}}\Longrightarrow 55 / x - 4 \Rightarrow x \equiv 4 \pmod{55} \end{align}

Използваме последното за да изразим $x$ : $x = 55k + 4$. И сега заместваме в първото сравнение:

(17)
\begin{align} 55k+4 \equiv 5 \pmod 7 \iff 55k \equiv 1 \pmod 7 \end{align}

И сега остава да решим новополученото модулно уравнение - получава се $k \equiv 6 \pmod 7$. Заместваме в $x$:

(18)
\begin{align} x = 55k + 4 = 55(7p + 6) + 4 = 55.7p + 55.6 + 4 = 385p + 331 \iff x \equiv 331 \pmod{385} \end{align}

с което задачата е решена!

Задача 11

Да се намерят последните 2 цифри на числото $2^999$.

Решение: Както вече знаем, задачата се свежда до намиране на остатъка, който дава $2^999$ при деление на $100$. Честа грешка е да се прилага Теоремата на Ферма-Ойлер, без да е изпълнено за взаимнопрости модул и основа.
Първо ще намерим остатъка при деление с $25$ (защото е взаимно прост със основата $2$), после ще видите :)

(19)
\begin{eqnarray} & &2^{\varphi(25)} \equiv 1 \pmod{25} \\ &\overset{\underset{\varphi(25)=20}{}}\Longrightarrow&2^{20} \equiv 1 \pmod{25} \quad \mbox{(c)}\\ &\overset{\underset{\mbox{(c)}\upharpoonright 49}{}}\Longrightarrow&2^{980} \equiv 1 \pmod{25} \quad (\spadesuit) \\ \hline \\ &&2^{10} = 1024 \equiv 24 \pmod{25} \quad \mbox{(a)}\\ &&2^9 = 512 \equiv 12 \pmod{25} \quad \mbox{(b)}\\ &\overset{\underset{(a)*(b)}{}}\Longrightarrow&2^{19} \equiv 12.24 \equiv 13 \pmod{25} \quad (\spadesuit \spadesuit) \\ \hline\\ &\overset{\underset{(\spadesuit) * (\spadesuit\spadesuit)}{}}\Longrightarrow& 2^{999} \equiv 13 \pmod{25}\\ \end{eqnarray}

Очевидно $2^{999} \equiv 0 \pmod 4$, т.е имаме, че търсеното от нас число e $25k + 13 = 4p$ (изразено от сравнението по модул 25 и по модул 4).
Остава да решим това диофантово уравнение по метода на Ойлер, за да получим: $k \equiv 3 \pmod 4$. Сега вече заместваме в горната формула и получаваме $25k + 13 = 25(4s + 3) + 13 = 100s + 88$, т.е числото дава остатък $88$ при деление на $100$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License