Number Theory: Divisibility (Examples)

This note has been used to help create the Factors wiki

This is the second 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.


Recap of Properties:

(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}).


Examples:

Example 1: Prove that 10020011\underbrace{0\cdots 0}_{200}1 is divisible by 10011001.

Proof: By (6)(6), we have

1002001=10201+1=(103)67+11\underbrace{0\cdots 0}_{200}1=10^{201}+1=(10^3)^{67}+1

=(103+1)[(103)66(103)65+103+1]=(10^3+1)\left[(10^3)^{66}-(10^3)^{65}+\cdots -10^3+1\right]

=1001[(103)66(103)65+103+1].=1001\left[(10^3)^{66}-(10^3)^{65}+\cdots -10^3+1\right].

Therefore, 10011001 divides 10020011\underbrace{0\cdots 0}_{200}1.


Example 2: Let aa and bb be integers such that a>b0a>b\geq 0. Show that

(22b+1)(22a1).(2^{2^b}+1)\mid (2^{2^a}-1).

Proof: Take x=22b+1x=2^{2^{b+1}}, y=1y=1 in (5)(5), and substitute nn by 2ab12^{a-b-1}. We have

22a1=(22b+11)[(22b+1)2ab11++22b+1+1].2^{2^a}-1=(2^{2^{b+1}}-1)\left[(2^{2^{b+1}})^{2^{a-b-1}-1}+\cdots+2^{2^{b+1}}+1\right].

Thus,

(22b+11)(22a1).(2^{2^{b+1}}-1)\mid (2^{2^a}-1).

Since

22b+11=(22b1)(22b+1),2^{2^{b+1}}-1=(2^{2^b}-1)(2^{2^b}+1),

hence

(22b+1)(22b+11).(2^{2^b}+1)\mid (2^{2^{b+1}}-1).

By (1)(1), we have

(22b+1)(22a1),(2^{2^b}+1)\mid(2^{2^a}-1),

and we are done.


Example 3: For a positive integer nn, let S(n)S(n) denote the sum of digits of nn. Show that 9n9\mid n if and only if 9S(n)9\mid S(n).

Proof: Write n=ak×10k++a1×10+a0n=a_k\times 10^k +\cdots + a_1\times 10 + a_0 (where 0ai90\leq a_i \leq 9, and ak0a_k \neq 0), then S(n)=a0+a1++akS(n)=a_0+a_1+\cdots+a_k. We have

nS(n)=ak(10k1)++a1(101)(1.1)n-S(n)=a_k(10^k-1)+\cdots+a_1(10-1)\cdots(1.1)

For 1ik1 \leq i \leq k, from (5)(5) we get 9(10i1)9 \mid (10^i-1). So every term of the kk terms in the RHS of (1.1)(1.1) is a multiple of 99, thus (2)(2) implies that their sum is also a multiple of 99, that is, 9(nS(n))9 \mid (n-S(n)). Hence, the result can be obtained easily.


Example 4: Let k1k \geq 1 be an odd integer. Prove that for any positive integer nn, 1k+2k++nk1^k+2^k+\cdots+n^k is not divisible by n+2n+2.

Proof: When n=1n=1 the statement is obviously true. For n2n \geq 2, denote the sum by AA. Then

2A=2+(2k+nk)+(3k+(n1)k)++(nk+2k).2A=2+(2^k+n^k)+(3^k+(n-1)^k)+\cdots+(n^k+2^k).

Since kk is a positive odd integer, from (6)(6) we know that for every i2i \geq 2, ik+(n+2i)ki^k+(n+2-i)^k is divisible by

i+(n+2i)=n+2.i+(n+2-i)=n+2.

Thus 2A2A has remainder 22 when divided by n+2n+2, which implies that AA is not divisible by n+2n+2 (note that n+2>2n+2>2).

Note by Victor Loh
4 years, 10 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

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 </span>...<span></span> ... <span> or </span>...<span></span> ... <span> 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

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...