Number Theory: Divisibility

This is the first note in the series Number Theory: Divisibility. All numbers involved in this note are integers, and letters used in this note stand for integers without further specification.


Numbers involved in this note are integers, and letters used in this book stand for integers without further specification.

Given numbers aa and bb, with b0b \neq 0, if there is an integer cc, such that a=bca=bc, then we say bb divides aa, and write bab \mid a. In this case we also say bb is a factor of aa, or aa is a multiple of bb. We use the notation bab \nmid a when bb does not divide aa (i.e., no such cc exists).

Several simple properties of divisibility could be obtained by the definition of divisibility (proofs of the properties are left to readers).


(1)(1) If bc,b \mid c, and ca,c \mid a, then ba,b \mid a, that is, divisibility is transitive.


(2)(2) If ba,b \mid a, and bc,b \mid c, then b(a±c),b \mid (a \pm c), that is, the set of multiples of an integer is closed under addition and subtraction operations.

By using this property repeatedly, we have, if bab \mid a and bcb \mid c, then b(au+cv)b \mid (au+cv), for any integers uu and vv. In general, if a1,a2,,ana_1,a_2,\cdots,a_n are multiples of bb, then b(a1+a2++an).b \mid (a_1+a_2+\cdots+a_n).


(3)(3) If bab \mid a, then a=0a=0 or ab\lvert a \rvert \geq \lvert b \rvert. Thus, if bab \mid a and aba \mid b, then a=b\lvert a \rvert = \lvert b \rvert.

Clearly, for any two integers aa and bb, aa is not always divisible by bb. But we have the following result, which is called the division algorithm. It is the most important result in elementary number theory.


(4)(4) (The division algorithm) Let aa and bb be integers, and b>0b > 0. Then there is a unique pair of integers qq and rr, such that a=bq+rand0r<b.a=bq+r \hspace{2mm} \text{and} \hspace{2mm} 0 \leq r < b.

The integer qq is called the (incomplete) quotient when aa is divided by bb, rr called the remainder. Note that the values of rr has bb kinds of possibilities, 0,1,,b10,1,\cdots,b-1. If r=0r=0, then aa is divisible by bb.

It is easy to see that the quotient qq in the division algorithm is in fact ab\lfloor\frac{a}{b}\rfloor (the greatest integer not exceeding ab\frac{a}{b}), and the heart of the division algorithm is the inequality about the remainder rr: 0r<b0 \leq r < b. We will go back to this point later on.

The basic method of proving bab \mid a is to factorize aa into the product of bb and another integer. Usually, in some basic problems this kind of factorization can be obtained by taking some special value in algebraic factorization equations. The following two factorization formulae are very useful in proving this kind of problems.


(5)(5) If nn is a positive integer, then xnyn=(xy)(xn1+xn2y++xyn2+yn1).x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1}).


(6)(6) If nn is a positive odd number, then xn+yn=(x+y)(xn1xn2y+xyn2+yn1).x^n+y^n=(x+y)(x^{n-1}-x^{n-2}y+\cdots-xy^{n-2}+y^{n-1}).

Note by Victor Loh
5 years ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Thanks much for posting this. I would love if you could name the book you had referred to in the beginning of this note!

Krishna Ar - 5 years ago

Log in to reply

I'm not sure if I want to reveal it because I'm scared I'm taking a little too much information :D

Victor Loh - 5 years ago

Log in to reply

I like the fact that although it's meant to be a comment with a negative connotation, there's still a smiley icon at the back which doesn't really fit the sentence (lol). Also, I think I have an idea which book he may have referred to...

Yuxuan Seah - 5 years ago

Log in to reply

@Yuxuan Seah But still, we have to acknowledge the rules of copyright. IF I feel like checking this book and find that you have really gleaned too much information from it, I might have to report you... D:

Yuxuan Seah - 5 years ago

Log in to reply

@Yuxuan Seah It's not THAT book, I promise.

Victor Loh - 5 years ago

Log in to reply

@Victor Loh Anyway, Brilliant is a site for sharing information, and I haven't exactly shared the examples and exercises yet.

Victor Loh - 5 years ago

Log in to reply

Uh-Oh!

Krishna Ar - 5 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...