Divisibility through seed numbers

Seed Numbers

Seed Numbers are used to find if a given number is divisible by a prime number. Although the concept is not used often, for some number, the divisibility rules cannot be applied and seed numbers come in handy there.

Every odd number (consider only odd prime numbers) gives unit digits of 1 and 9 in two of their first 10 multiples. For example, 3 × 3 = 9, and 3 × 7 = 21. For 17, 17 × 3 = 51, and 17 × 7 = 119. You can do this for any odd prime number and see that it is true. Now numbers ending in 1 or 9 can be written as multiples of 10 ± 1. For example 51 = 5 × 10 + 1, 119 = 12 × 10 - 1, etc. Now these numbers which are multipled by 10 (5 and 12 in this case) are the seed numbers for a particular prime number. The numbers are taken negative in the case of + 1 and positive in the case of -1. Therefore, every prime number has two seed numbers. In the above example, the seed numbers of 17 are -5 and 12. Here are seed numers of some prime numbers listed down.

Numbers	Multiples ending in 1	Multiples ending in 9	Seed numbers
3	21 = 2 × 10 + 1	9 = 1 × 10 - 1	- 2, 1
7	21 = 2 × 10 + 1	49 = 5 × 10 - 1	- 2, 5
13	91 = 9 × 10 + 1	39 = 4 × 10 - 1	- 9, 4
17	51 = 5 × 10 + 1	119 = 12 × 10 - 1	- 5, 12
19	171 = 17 × 10 + 1	19 = 2 × 10 - 1	- 17, 2
23	161 = 16 × 10 + 1	69 = 7 × 10 - 1	- 16, 7

How to use seed numbers:

Suppose you want to find out if 9044 is divisible by 17. You know that the seed number of 17 is -5. Here is what you do:

• Take out the unit digit of the number, multiply it with the seed number and add it to the number left after removing the unit digit. Therefore, take out the unit digit of 9044 i.e. 4, multiply it by -5, 4 × -5 = -20, and add it to the number left, i.e. 904. 904 - 20 = 884.
• Keep repeating this operation. For 884, take out 4, multiply it by -5 --> 4 × -5 = -20, add it to number left --> 88 - 20 = 68.
• In the end you will come up with a single digit or two digit number. If this number is divisible by the prime number, the original number is divisible by the prime number. Here, 68 is divisible by 17, therefore 9044 is divisible by 17.

Let's do it once more.

Find if 43985 is divisible by 19.

We use the seed number 2 for 19.

• First step: 4398 + 5 × 2 = 4408
• Second step: 440 + 8 × 2 = 456
• Third step: 45 + 6 × 2 = 57

Now 57 is divisible by 2. Therefore, 43985 is divisble by 2.

You can use seed numbers to find divisibility by any prime number.