X hits on this document

62 views

0 shares

0 downloads

0 comments

8 / 15

a = [a

a0] = 10n[a

an] + [an 1

[a

an] + [an 1

number a = [a

a0]. Assuming k n, we get

a0]

a0]

(mod d)

Now letting t be the greatest integer such that k tn, and repeating this process on the leftmost term we find

an]) + [an 1

a0]

an] + [an 1

a0]

[atn 1

a

t 1)n] + · · ·

[a2n 1

an] + [an 1

[a

( [a

= [a

( 1)t[a

(mod d)

atn] + ( 1)t 1

a = [a

. . .

a2n] + [a2n 1

a2n]

[a2n

1

a0]

an] + [an 1

a0]

Running total: We now have divisibility tests for 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 16, 20, 27, 25, 32, 33, 37, 40, 50, 64, 73, 77, 80, 91, 99, 100, 101.

3.4

Trim from the Right

A basic result from elementary number theory tells us that if the greatest common divisor of d and 10 is 1, then there exists a number u such that 10u 1 (mod d). Such a number u is called an inverse of 10 modulo d and

we write u 10 1 (mod d). For instance, 10(4) = 40 1 (mod 13) so 4 10

1, mod 13. In fact, any

number congruent to 4 mod 13 (e.g.

9), is also an inverse of 10, mod 13.

8

a0]

Document info
Document views62
Page views66
Page last viewedTue Jan 17 20:02:16 UTC 2017
Pages15
Paragraphs695
Words3760

Comments