One can test if an integer is divisible by prime by subtracting the last two digits (as a number) from with those digits shaved off, and see if the result is divisible by . For example, is divisible by because and .
What are the smallest factors you should multiply the last two digits of (as a number) with, before subtracting from the shaved-off in the divisibility tests for and
Give your answer as the product of the factors.
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.
Related wiki: Divisibility Rules > Finding Divisibility Rules
Let x be the number you get by clipping off the last two digits of n , and let y be the number from those two digits. Then if p divides n , with n = 1 0 0 x + y , p should also divide x + k y , with k being the negative integer we're looking for. This results in two congruence equations:
1 0 0 x + y ≡ 0 ( m o d p )
x + k y ≡ 0 ( m o d p )
Or:
y ( 1 − 1 0 0 k ) ≡ ( m o d p )
Since p doesn't divide y in general, it should divide 1 − 1 0 0 k :
1 0 0 k ≡ 1 ( m o d p )
This equation reads as follows: find such k that dividing 1 0 0 k by p leaves unit remainder. With p = 4 3 , k = 4 0 (which means adding 4 0 y to x ), or k = 4 0 − 4 3 = − 3 (which means subtracting 3 y from x ). With p = 6 7 , k = − 2 , so the answer to the problem is 3 ⋅ 2 = 6 .
Finding k means finding modular inverse of 1 0 0 modulo p . One can use extended Euclidean algorithm for that, but for small values the result can also be found readily by hand.