Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Divisibility"
 
(8 intermediate revisions by 6 users not shown)
Line 1: Line 1:
−
== Description ==
+
In [[number theory]], '''divisibility''' is the ability of a number to evenly divide another number. The study of divisibility resides at the heart of number theory, constituting the backbone to countless fields of mathematics. Within number theory,
−
Divisibility is the ability of a number to be evenly divided by another number. For example, four divided by two is equal to two, and therefore, four is divisible by two.
+
the study of [[arithmetic functions]], [[modular arithmetic]], and [[Diophantine equations]] all depend on divisibility for rigorous foundation.
  
−
== Notation ==
+
A '''divisor''' of an integer <math>a</math> is an integer <math>b</math> that can be multiplied by some integer to produce <math>a</math>. We may equivalently state that <math>a</math> is a '''multiple''' of <math>b</math>, and that <math>a</math> is '''divisible''' or '''evenly divisible''' by <math>b</math>.
  
−
We commonly write <math>n|k</math>. This means that n is a divisor of k. So for the example above, we would write 2|4.
+
== Definition ==
 +
An integer <math>a</math> is divisible by a nonzero integer <math>b</math> if there exists some integer <math>n</math> such that <math>a = bn</math>. We may write this relation as <cmath>b \mid a.</cmath> An alternative definition of divisibility is that the fraction <math>a / b</math> is an integer — or using [[modular arithmetic]], that <math>b \equiv 0 \pmod a</math>. If <math>b</math> does ''not'' divide <math>a</math>, we write that <math>b \nmid a</math>.
  
−
==Rules for common divisors==
+
=== Examples ===
 +
* <math>6</math> divides <math>48</math> as <math>6 \times 8 = 48</math>, so we may write that <math>6 \mid 48</math>.
 +
* <math>-2</math> divides <math>6</math> as <math>6/(-2) = -3</math>, so we may write that <math>-2 \mid 6</math>.
 +
* The positive divisors of <math>35</math> are <math>1</math>, <math>5</math>, <math>7</math>, and <math>35</math>.
 +
* By convention, we write that every nonzero integer divides <math>0</math>; so <math>-1923 \mid 0</math>.
  
−
=== By <math>2^n</math> ===
+
== See Also ==
−
A number is divisible by <math>2^n</math> if the last <math>{n}</math> digits of the number are divisible by <math>2^n</math>.
+
* [[Arithmetic functions]]
 +
* [[Modular arithmetic]]
 +
* [[Diophantine equations]]
  
−
=== By 3 ===
+
[[Category:Number theory]]
−
A number is divisible by 3 if the sum of its digits is divisible by 3.
+
[[Category:Definition]]
−
===By <math>5^n</math> ===
 
−
A number is divisible by 5^n if the last n digits are divisible by that power of 5.
 
−
 
 
−
=== By 9 ===
 
−
A number is divisible by 9 if the sum of its digits is divisible by 9.
 
−
 
 
−
=== By 7 ===
 
−
Rule 1: Partition <math>n</math> into 3 digit numbers from the right (<math>d_3d_2d_1,d_6d_5d_4,\dots</math>).  If the alternating sum (<math>d_3d_2d_1 - d_6d_5d_4 + d_9d_8d_7 - \dots</math>) is divisible by 7 then the number is divisible by 7.<br>
 
−
<br>
 
−
Rule 2: Truncate the last digit of <math>{n}</math>, and subtract twice that digit from the remaining number.  If the result is divisible by 7, then the number is divisible by 7.  This process can be repeated for large numbers.<br>
 
−
 
 
−
=== By 11 ===
 
−
A number is divisible by 11 if the alternating sum of the digits is divisible by 11.
 
−
 
 
−
=== By 13 ===
 
−
See rule 1 for divisibility by 7, a number is divisible by 13 if the same specified sum is divisible by 13.
 

Latest revision as of 15:21, 29 April 2023

In number theory, divisibility is the ability of a number to evenly divide another number. The study of divisibility resides at the heart of number theory, constituting the backbone to countless fields of mathematics. Within number theory, the study of arithmetic functions, modular arithmetic, and Diophantine equations all depend on divisibility for rigorous foundation.

A divisor of an integer $a$ is an integer $b$ that can be multiplied by some integer to produce $a$. We may equivalently state that $a$ is a multiple of $b$, and that $a$ is divisible or evenly divisible by $b$.

Definition

An integer $a$ is divisible by a nonzero integer $b$ if there exists some integer $n$ such that $a = bn$. We may write this relation as \[b \mid a.\] An alternative definition of divisibility is that the fraction $a / b$ is an integer — or using modular arithmetic, that $b \equiv 0 \pmod a$. If $b$ does not divide $a$, we write that $b \nmid a$.

Examples

  • $6$ divides $48$ as $6 \times 8 = 48$, so we may write that $6 \mid 48$.
  • $-2$ divides $6$ as $6/(-2) = -3$, so we may write that $-2 \mid 6$.
  • The positive divisors of $35$ are $1$, $5$, $7$, and $35$.
  • By convention, we write that every nonzero integer divides $0$; so $-1923 \mid 0$.

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Divisibility&oldid=192610"