Shave off Last Two

One can test if an integer n n is divisible by prime 101 101 by subtracting the last two digits (as a number) from n n with those digits shaved off, and see if the result is divisible by 101 101 . For example, 162794931 162794931 is divisible by 101 101 because 1627949 31 = 1627918 1627949 - 31 = 1627918 and 101 1627918 101 \, | \, 1627918 .

What are the smallest factors you should multiply the last two digits of n n (as a number) with, before subtracting from the shaved-off n n in the divisibility tests for p = 43 p = 43 and p = 67 ? p = 67?

Give your answer as the product of the factors.


The answer is 6.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Borut Levart
Sep 16, 2017

Related wiki: Divisibility Rules > Finding Divisibility Rules

Let x x be the number you get by clipping off the last two digits of n n , and let y y be the number from those two digits. Then if p p divides n n , with n = 100 x + y n = 100 \ x + y , p p should also divide x + k y x + k \ y , with k k being the negative integer we're looking for. This results in two congruence equations:

100 x + y 0 ( m o d p ) 100 \ x + y \equiv 0 \pmod{p}

x + k y 0 ( m o d p ) x + k \ y \equiv 0 \pmod{p}

Or:

y ( 1 100 k ) ( m o d p ) y \ (1 - 100 \ k) \equiv \pmod{p}

Since p p doesn't divide y y in general, it should divide 1 100 k 1 - 100 \ k :

100 k 1 ( m o d p ) 100 \ k \equiv 1 \pmod{p}

This equation reads as follows: find such k k that dividing 100 k 100 \ k by p p leaves unit remainder. With p = 43 p = 43 , k = 40 k = 40 (which means adding 40 y 40 \ y to x x ), or k = 40 43 = 3 k = 40 - 43 = -3 (which means subtracting 3 y 3 \ y from x x ). With p = 67 p = 67 , k = 2 k = -2 , so the answer to the problem is 3 2 = 6 3 \cdot 2 = 6 .

Finding k k means finding modular inverse of 100 100 modulo p p . One can use extended Euclidean algorithm for that, but for small values the result can also be found readily by hand.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...