5.3: Подільність

Last updated
Save as PDF

Page ID: 64104

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

У цьому розділі ми вивчимо поняття подільності. $b$Дозволяти$a$ і бути два цілих числа такі, що$a \neq 0$. Наступні твердження еквівалентні:

$a$ділить$b$,
$a$є дільником$b$,
$a$є фактором$b$,
$b$є кратним$a$, і
$b$ділиться на$a$.

Всі вони означають

Існує ціле число$q$ таке, що$b=aq$

З точки зору ділення ми говоримо, що$a$ ділить$b$ тоді і тільки тоді, коли залишок дорівнює нулю при$b$ діленні на$a$. Ми приймаємо позначення\[a \mid b \qquad \mbox{[pronounced as "$a$ divides $b$'']}\] Не використовуйте косу риску$/$ або зворотну косу риску$\backslash$ в позначеннях. Щоб сказати, що$a$ не ділиться$b$, додаємо косу риску поперек вертикальної смуги, як в

\[a \nmid b \qquad \mbox{[pronounced as "$a$ does not divide $b$'']}\]Не плутайте позначення$a\mid b$ з$\frac{a}{b}$. Позначення$\frac{a}{b}$ являє собою дріб. Він також пишеться як$a/b$ з (вперед) косою рискою рисою рискою рисою рисою. Він використовує ділення з плаваючою комою (тобто дійсне або десяткове) ділення. Наприклад,$\frac{11}{4}=2.75$.

Визначення подільності дуже важливо. Багато студентів не можуть закінчити дуже прості докази, оскільки вони не можуть згадати визначення. Отже, тут ми знову йдемо:

$a\mid b\;\Leftrightarrow\;b=aq$для деякого цілого числа$q$.

Обидва цілих числа$a$ і$b$ можуть бути додатними або негативними, і навіть$b$ може бути 0. Єдине обмеження - це$a\neq0$. Крім того,$q$ має бути ціле число. Наприклад, але це$3 = 2\cdot\frac{3}{2}$, безумовно, абсурдно сказати, що 2 ділить 3.

Приклад$\PageIndex{1}\label{eg:divides-01}$

З тих пір$14=(-2)\cdot(-7)$, зрозуміло, що$-2\mid 14$.

практичні вправи$\PageIndex{1}\label{he:divides-01}$

Переконайтеся, що,\[5 \mid 35, \quad 8\nmid 35, \quad 25\nmid 35, \quad 7 \mid 14, \quad 2 \mid -14, \quad\mbox{and}\quad 14\mid 14,\] знайшовши частку$q$ і залишок$r$ такі$b=aq+r$, що, і$r=0$ якщо$a\mid b$.

Приклад$\PageIndex{2}\label{eg:divides-02}$

Ціле число парне тоді і тільки тоді, коли воно ділиться на 2, і воно непарне тоді і тільки тоді, коли воно не ділиться на 2.

практичні вправи$\PageIndex{2}\label{he:divides-02}$

Що таке залишок, коли непарне ціле число ділиться на 2? Виконайте наступні речення:

Якщо$n$ парне, то$n=\bline{0.5in}$ для деякого цілого числа.
Якщо$n$ непарна, то$n=\bline{0.5in}$ для.

Добре запам'ятайте їх, оскільки ви будете часто використовувати їх у цьому курсі.

практичні вправи$\PageIndex{3}\label{he:divides-03}$

Виконайте наступне речення:

Якщо не$n$ ділиться на 3, то, або$n=\bline{0.5in}\,$$n=\bline{0.5in}\,$, для якогось цілого числа.

Порівняйте це з$\bmod$ операціями$\bdiv$ та. Які можливі значення$n\bmod3$?

Приклад$\PageIndex{3}\label{eg:divides-03}$

З огляду на будь-яке ціле число$a\neq 0$, ми завжди є$a\mid 0$ тому, що$0 = a\cdot 0$. Зокрема, 0 ділиться на 2, отже, вважається парним цілим числом.

Приклад$\PageIndex{4}\label{eg:divides-04}$

Аналогічно$\pm1$ і$\pm b$ ділимо$b$ на будь-яке ненульове ціле число$b$. Їх називають тривіальними дільниками$a$. Дільник$b$ того, що не є тривіальним дільником, називається нетривіальним дільником$b$.

Наприклад, ціле число 15 має вісім дільників:$\pm1, \pm3, \pm5, \pm15$. Його тривіальними дільниками є$\pm1$ і$\pm15$, а нетривіальними дільниками є$\pm3$ і$\pm5$.

Визначення

Натуральне ціле число$a$ є правильним дільником$b$ if$a\mid b$ і$a<|b|$. Якщо$a$ є правильним дільником$b$, ми говоримо, що $a$ділить$b$ правильно.

Зауваження

Деякі теоретики чисел включають негативні числа як правильні дільники. У цій умовності,$a$ є власним дільником$b$ if$a\mid b$, і$|a|<|b|$. Щоб додати плутанини, деякі теоретики чисел виключають$\pm1$ як правильні дільники. Будьте обережні, коли зіткнетеся з цими умовами.

Приклад$\PageIndex{5}\label{eg:divides-05}$

Зрозуміло, що 12 ділить 132 належним чином, а 2 ділить$-14$ належним чином. Ціле число 11 не має належного дільника.

практичні вправи$\PageIndex{4}\label{he:divides-04}$

Які правильні дільники 132?

Визначення

Ціле число$p>1$ є простим, якщо його додатні дільники дорівнюють 1 і$p$ сам. Будь-яке ціле число більше 1, яке не є простим, називається складовим.

Зауваження

Додатне ціле число$n$ є складовим, якщо воно має дільник$d$, який задовольняє$1<d<n$. Також, згідно з визначенням, ціле число 1 не є ні простим, ні складовим.

Приклад$\PageIndex{6}\label{eg:divides-06}$

Цілі числа$2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots\,$ є прості.

практичні вправи$\PageIndex{5}\label{he:divides-07}$

Які наступні п'ять простих чисел після 23?

Теорема$\PageIndex{1}$

Є нескінченно багато простих чисел.

Доказ: Ми відкладаємо його доказ на більш пізній розділ, після того як доведемо фундаментальний результат в теорії чисел.

Теорема$\PageIndex{2}$

Для всіх цілих чисел$a$$b$, і$c$ де$a \neq 0$, у нас є

Якщо$a\mid b$, то$a\mid xb$ для будь-якого цілого числа$x$.
Якщо$a\mid b$ і$b\mid c$, то$a\mid c$. (Це називається перехідною властивістю подільності.)
Якщо$a\mid b$ і$a\mid c$, то$a\mid (sb+tc)$ для будь-яких цілих чисел$x$ і$y$. (Вираз$sb+tc$ називається лінійним поєднанням$b$ і$c$.)
Якщо$b\neq 0$ і$a\mid b$ і$b\mid a$, то$a = \pm b$.
Якщо$a\mid b$ і$a,b > 0$, то$a \leq b$.

Доказ: Доведемо лише (1), (4) і (5), і залишимо докази (2) і (3) як вправи.
Доказ (1): Припустимо$a\mid b$, тоді існує ціле число$q$ таке, що$b=aq$. Для будь-якого цілого числа$x$, у нас$xq$ є\[xb = x\cdot aq = a \cdot xq,\] де ціле число. Отже,$a\mid xb$.

Доказ (4): Припустимо$a\mid b$, і$b\mid a$. Тоді існують цілі числа$q$ і$q'$ такі$b=aq$, що, і$a=bq'$. Звідси випливає, що\[a = bq' = aq\cdot q'.\] це означає$qq'=1$. Обидва$q$ і$q'$ є цілими числами. Таким чином, кожен з них повинен бути або 1$-1$, або, який робить$b=\pm a$.

Доказ (5): Припустимо$a\mid b$ і$a,b>0$. Потім$b=aq$ для деякого цілого числа$q$. Так як$a,b>0$, у нас теж є$q>0$. Будучи цілим числом, ми повинні мати$q\geq1$. Потім$b = aq \geq a\cdot 1 = a$.

Приклад$\PageIndex{7}\label{eg:divides-07}$

Використовуйте визначення подільності, щоб показати, що дані будь-які цілі числа$a$, і$b$, де$c$, якщо$a\mid b$ і$a\neq0$$a\mid c$, то$a\mid(sb^2+tc^2)$ для будь-яких цілих чисел$s$ і$t$.

Рішення

Ми намагаємося довести це з перших принципів, тобто використовуючи лише визначення подільності. Ось повний доказ.

Припустимо$a\mid b$ і$a\mid c$. Існують цілі числа$x$ і$y$
такі, що$b=ax$ і$c=ay$. Тоді
\[ sb^2+tc^2 = s(ax)^2+t(ay)^2 = a(sax^2+tay^2), \]
де$sax^2+tay^2$ - ціле число. Звідси$a\mid(sb^2+tc^2)$.

Ключовим кроком є підстановка$b=ax$ і$c=ay$ в вираз$sb^2+tc^2$. Ви можете запитати, як ми можемо знати, що це правильно?

Ось причина. Ми хочемо це показати$a\mid(sb^2+tc^2)$. Це означає, що нам потрібно знайти ціле число, яке при$a$ множенні на дає$sb^2+tc^2$. Це вимагає запису$sb^2+tc^2$ як добуток$a$ і інше ціле число, яке ще не визначено. Оскільки$s$ і не$t$ мають ніякого відношення до$a$, наша єдина надія полягає в$b$ і$c$. Ми це знаємо,$b=ax$ і$c=ay$, отже, ми повинні замінити їх на$sb^2+tc^2$.

практичні вправи$\PageIndex{6}\label{he:divides-06}$

Нехай$a$,$b$, і$c$ бути цілими числами такі, що$a\neq 0$. Доведіть, що якщо$a\mid b$ або$a\mid c$, то$a\mid bc$.

Резюме та огляд

Ціле число$b$ ділиться на ненульове ціле число$a$ тоді і тільки тоді, коли існує ціле число$q$ таке, що$b=aq$.
Ціле число$n>1$ вважається простим, якщо його єдиними дільниками є$\pm1$ і$\pm n$; в іншому випадку, ми говоримо, що$n$ є складовим.
Якщо$n$ натуральне число є складовим, воно має правильний дільник$d$, який задовольняє нерівності$1<d<n$.

Вправа$\PageIndex{1}\label{ex:divides-01}$

Нехай$a$,$b$, і$c$ бути цілими числами такі, що$a\neq0$. Використовуйте визначення подільності, щоб довести, що якщо$a\mid b$ і$c\mid (-a)$, то$(-c)\mid b$. Використовуйте лише визначення подільності, щоб довести ці наслідки.

Вправа$\PageIndex{2}\label{ex:divides-02}$

Дозволяти$a$$b$,$c$,, і$d$ бути цілими числами с$a,c\neq0$. Доведіть, що

Якщо$a\mid b$ і$c\mid d$, то$ac\mid bd$.
Якщо$ac \mid bc$, то$a\mid b$.

Вправа$\PageIndex{3}\label{ex:divides-03}$

Нехай$a$,$b$, і$c$ бути цілими числами такі, що$a,b\neq0$. Доведіть, що якщо$a\mid b$ і$b\mid c$, то$a\mid c$.

Вправа$\PageIndex{4}\label{ex:divides-04}$

Нехай$a$,$b$, і$c$ бути цілими числами такі, що$a\neq0$. Доведіть, що якщо$a\mid b$ і$a\mid c$, то$a\mid (sb+tc)$ для будь-яких цілих чисел$s$ і$t$.

Вправа$\PageIndex{5}\label{ex:divides-05}$

Доведіть,$n$ що якщо непарне ціле число,$n^2-1$ то ділиться на 4.

Вправа$\PageIndex{6}\label{ex:divides-06}$

Скористайтеся результатом завдання [ex:divides-05], щоб показати, що жодне з чисел 11, 111, 1111 та 11111 не є ідеальним квадратом. Узагальнити, і довести свою здогадку.

Підказка: $x$Дозволяти бути одним з цих чисел. Припустимо,$x$ це ідеальний квадрат, то$x=n^2$ для деякого цілого числа$n$. Як можна застосувати результат з проблеми [ex:divides-05]?

Вправа$\PageIndex{7}\label{ex:divides-07}$

Доведіть, що квадрат будь-якого цілого числа має форму$3k$ або$3k+1$.

Вправа$\PageIndex{8}\label{ex:divides-08}$

Використовуйте Problem [ex:divides-07], щоб довести, що не$3m^2-1$ є ідеальним квадратом для будь-якого цілого числа$m$.

Вправа$\PageIndex{9}\label{ex:divides-09}$

Використовуйте індукцію, щоб довести, що$3\mid (2^{2n}-1)$ для всіх цілих чисел$n\geq1$.

Вправа$\PageIndex{10}\label{ex:divides-10}$

Використовуйте індукцію, щоб довести, що$8\mid (5^{2n}+7)$ для всіх цілих чисел$n\geq1$.

Вправа$\PageIndex{11}\label{ex:divides-11}$

Використовуйте індукцію, щоб довести, що$5\mid (n^5-n)$ для всіх цілих чисел$n\geq1$.

Вправа$\PageIndex{11}\label{ex:divides-12}$

Використовуйте індукцію, щоб довести, що$5\mid (3^{3n+1}+2^{n+1})$ для всіх цілих чисел$n\geq1$.