# Divisible by 1000003? Easy, just multiply the last digit by 300001 and add!

Given a prime P greater than 10, your program or function must figure out its divisibility rule x, defined as the integer with smallest absolute value which yields a multiple of the original prime when multiplied by the last digit of the prime and added to the rest of the original prime.

## Example

Given an input 31, the last digit is 1 and the rest of the number is 3. Thus your program must find the integer x with minimum absolute value such that 1*x + 3 is a multiple of 31. In this case, x=-3 works, so the program or function would return -3.

Given an input 1000003, the last digit is 3 and the rest of the number is 100000. Thus your program would find x=300001 because 3*300001+100000 = 1000003 which is a multiple of 1000003.

## Mathematical Background

The value of x can be used as a divisibility test. If a number N is divisible by P, then adding x times the last digit of N to the rest of N will yield a multiple of P if and only if N is divisible by P in the first place.

For P=11, we get x=-1, which is equivalent to the well-known divisibility rule for 11: a number is divisible by 11 alternating difference of its digits is divisible by 11.

## Rules

• The output may be in any form that clearly encodes both the sign and value of the output.
• The input prime will be between 10 and 2^30.
• You do not need to handle if the input is not a prime or is not in the range.
• You do not need to handle if both x and -x are valid outputs (should not happen).
• Brute force is permitted, but more creative solutions are appreciated.
• This is , so shortest code in each language wins! Do not let answers in golfing languages discourage you from posting in other languages.

## Test Cases

Input   Output
11  -1
13  4
17  -5
19  2
23  7
29  3
31  -3
37  -11
41  -4
43  13
47  -14
53  16
59  6
61  -6
67  -20
71  -7
73  22
79  8
83  25
89  9
97  -29
101 -10
103 31
107 -32
109 11
113 34
127 -38
131 -13
1000003 300001
2000003 600001
2999999 300000
9999991 -999999

• A useful simplification: we're looking for the smallest x in absolute value where 10*x-1 is divisible by the input. – xnor Aug 19 '17 at 20:31
• Can anybody provide a hint why (3 / (n % 5 * 2 - 5) * n + 1) / 10 and (n % 5 * 2 - 5^2) * n / 10 + 1 are able to find a minimal absolute value for something like this? My first intuition would have been to calculate the least common multiple using the greatest common divisor calculated with Euclid's algorithm. – David Foerster Aug 20 '17 at 14:56
• @DavidFoerster Given a number, you can remove the last digit, multiply it by a number x, add it on, and still get a number divisible by n. If we then multiply the new number by 10 and subtract the original number it still remains divisible by n. xnor's comment then follows from some algebra. The next step is to rearrange the formula so that it gives x in terms of n: x = (k*n+1)/10. We want the smallest absolute x so therefore we want the smallest absolute k, and this must be whichever one of -3, -1, 1 or 3 (depending on n's last digit) that makes the division exact. – Neil Aug 26 '17 at 23:29

## JavaScript (ES6), 3225 23 bytes

f=
n=>(3/(n%5*2-5)*n+1)/10
<input type=number min=1 oninput=o.textContent=this.value%5*(this.value%2)?f(this.value):><pre id=o>

3/(n%5*2-5) would be written 9/n(mod -10) if I had access to balanced modulo division. Edit: Saved 2 bytes thanks to @EgorSkriptunoff

• You can save 2 bytes by replacing n=>((n%10*2%14-3)*n+1)/10 with n=>(3/(n%5*2-5)*n+1)/10 – Egor Skriptunoff Aug 19 '17 at 20:57
• This is a polyglot for .Net C#. – Kevin Cruijssen Sep 1 '17 at 9:01
• @KevinCruijssen Probably a near-miss polyglot for Java 8 too... oh wait, I see your answer now! – Neil Sep 1 '17 at 9:33
• @Neil You're right. I usually post Java answers, so I was already working on a port of xnor when I saw your answer. Posted it either way as a boring port crediting you. – Kevin Cruijssen Sep 1 '17 at 10:38

# Python 2, 27 bytes

lambda n:(n%5*2-5^2)*n/10+1


Try it online!

The operations are done left to right: (((n%5)*2)-5)^2.

I used my arithmetic brute forcer to find the expression n%5*2-5^2 to perform {1:-1,3:3,2:-3,4:1}[k], taking the negative inverse of a residue mod 5 into the range [-2..2].

• Is this arithmetic brute forcer publicly available somewhere? – Lynn Aug 20 '17 at 20:11
• Is that the only expression it found or does it just print the first one of a given length? (3/(n%5*2-5) is the same length as (n%5*2-5^2).) – Neil Aug 21 '17 at 17:09
• @Lynn No, I might clean and up and post it when I have time. – xnor Aug 22 '17 at 0:14
• @Neil It only found equivalents and n%5*2-6^3. I only looked up to the length though of the expression without parens, whereas 3/(n%5*2-5) is two characters longer but saves on outer parens due to precedence. Searching expressions of this length should take a while. This use-case does suggest an option to only find expressions that can be used in a given context via their outermost operation having high enough precedence. – xnor Aug 22 '17 at 0:17

# Jelly, 10 8 bytes

,N⁵æiAÞḢ


Try it online!

### Explanations

,N       Get [Input, -Input].
⁵æi      Modular inverse of 10 mod each of [Input, -Input].
AÞ       Sort by absolute value.
Ḣ        First.

• +1 I have never seen a Jelly submission with register that actually saves bytes – Mr. Xcoder Aug 19 '17 at 17:27
• @Mr.Xcoder It was because I didn't golf it well. – jimmy23013 Aug 19 '17 at 17:48

# Brachylog, 14 bytes

∧.ℤ≜×₁₀-₁;?%0∧


Try it online!

# Python 2, 6954 53 bytes

Edit: -15 bytes thanks to @Mr.Xcoder

Edit: -1 byte by using recursion

f=lambda a,x=-1:(a%10*x+a/10)%a and f(a,-x-(x>0))or x


Try it online!

• 54 bytes. I don't see why you have those variables when you only use them once – Mr. Xcoder Aug 19 '17 at 17:24
• Yeah, was in a bit of a hurry when I wrote it – Halvard Hummel Aug 19 '17 at 17:27

# Python 2, 31 29 27 bytes

lambda n:3/(n%5*2-5)*n/10+1


Try it online!

# Japt, 16 9 bytes

Saved way too many bytes thanks to an observation by @xnor

_*AÉ vU}c


Test it online! May take a couple of seconds on larger inputs.

### Explanation

_  *AÉ  vU}c    Implicit: U = input integer
Z{Z*A-1 vU}c    Ungolfed
Z{        }c    Loop through each integer Z in [0, -1, 1, -2, ...] and yield the first where
Z*A             Z times 10
-1           minus 1
vU        is divisible by the input.
Implicit: output result of last expression


# Java 8, 23 21 bytes

n->3/(n%5*2-5)*++n/10


Port of @Neil's JavaScrip (ES6) answer, but -2 bytes thanks to @Nevay due to implicit flooring of integers.

Try it here.

• 21 bytes: n->3/(n%5*2-5)*++n/10 – Nevay Sep 1 '17 at 12:19
• @Nevay Even when I create a port of the top answer, you still have to golf me.. xD (Read: Thanks and nice job!) – Kevin Cruijssen Sep 1 '17 at 12:28

# Pyke, 12 bytes

3Q5%}5-f*hTf


Try it here!

# Pyth, 14 bytes

h/*x-y%QK5K2QT


Try it here.

# Python 2, 44 43 bytes

(Crossed out 44 is still 44.) Thanks to Fireflame241 for saving a byte!

P=input();i=P/3
while i*10%P-1:i-=1
print i


Try it online!

There is exactly one number between 0 and P-1 which is an inverse of 10. But if that inverse u happens to be greater than P/2, then (u-P) is also an inverse, and has a smaller absolute value than u. So it turns out that we're really looking for the unique number x between -P/2 and P/2 which is an inverse of 10.

The code above does exactly that, starting at (the floor of) P/2, and stepping downward until an inverse is reached. This must happen for some number greater than -P/2 so long as P is a prime greater than 10. More precisely, it will terminate if and only if P is coprime to 10.

Edit: It actually turns out that x is guaranteed to be between -P/3 and P/3, so the current version starts at P/3 and steps down from there. See the section labeled Improved Bound for an explanation of this.

### Mathematical explanation

It was not immediately obvious to me why the divisibility test worked. Here's an explanation, in case anyone else was wondering.

Let P be a prime, greater than 10, whose last digit is b. Thus

P = 10a + b

where a > 0, and 0 <= b < 10. In fact b is either 1, 3, 7, or 9, because a prime greater than 10 must end in one of these digits.

Now suppose bx + a = 0 (mod P). Then

a = -bx (mod P)

10a + b = 10(-bx) + b (mod P)

0 = 10(-bx) + b (mod P)

0 = b(1 - 10x) (mod P)

Since P is prime, the integers mod P are an integral domain. So either b = 0 (mod P), or 1 - 10x = 0 (mod P).

We know 0 <= b < 10 < P, so if b = 0 (mod P) then b = 0. But we said b is either 1, 3, 7, or 9, so this is impossible. Therefore 1 - 10x = 0 (mod P), so 10x = 1 (mod P). In other words, x is the inverse of 10, modulo P.

Now suppose N is a nonnegative integer whose last digit is d, so N = 10c + d. We have a chain of equivalent statements:

10c + d = 0 (mod P)

<==> 10xc + dx = 0 (mod P)

<==> c + dx = 0 (mod P)

QED.

### Usefulness?

I was also wondering whether the divisibility test (given N = 10c + d, replace N by dx + c) would actually be productive in practice. Or at least, does it reliably replace N by a number smaller than N (in absolute value)?

Suppose N = 10c + d, where c >= 0 and 0 <= d < 10. Therefore 10c = N - d <= N. By the triangle inequality,

|c + dx| <= |c| + |dx| = c + d|x| <= N/10 + d|x|

< N/10 + 10|x| <= N/10 + 10P/2 = N/10 + 5P

Thus if 5P <= 9N/10, then |c + dx| < N.

In particular, if N >= 6P, then |c + dx| < N. Thus, given P we begin by calculating 2P, 3P, ..., 6P, along with x. Then given N, we run the divisibility test repeatedly until we reach a number less than or equal to 6P, and check whether the result is any of the numbers 0, P, 2P, ..., 6P.

(Of course, whenever we reach a negative number, we replace it by its absolute value, which is fine since q is divisible by P if and only if (-q) is.)

### Improved Bound

I noticed that |x|/P never seemed to be close to 1/2. In fact it seemed like it was always less than 1/3...or upon closer examination, it was always very close to either 1/10 or 3/10. The biggest it ever got seemed to be 4/13 (which happens when P=13 and x=4). Why would this be?

Let u be an integer and suppose that 10u = kP + 1 for some integer k, so u is an inverse of 10, modulo P. Then we also know that k is relatively prime to 10, since k(-P) is equivalent to 1 modulo 10.

Now, we know that the inverses of 10 modulo P all differ by multiples of P, so we can take the integer u and either add or subtract multiples of P at will, and the result will always still be an inverse of 10 modulo P. Suppose we choose to subtract P from u: we get

10(u - P) = 10u - 10P = kP + 1 - 10P

10(u - P) = (k - 10)P + 1

In other words, decreasing (respectively, increasing) u by P corresponds to decreasing (increasing) k by 10. We wish to add/subtract multiples of P from u until the left-hand side is minimized in absolute value; but the left-hand side is minimized exactly when the right-hand side is minimized, and so we want to add/subtract 10 from k until the right-hand side is minimized in absolute value.

But we know that this will happen when k is between -5 and 5, and therefore (since k is relatively prime to 10) this means k is either -3, -1, 1, or 3. (This is the content of @Neil's comment under the OP. Thanks, Neil!)

Thus when |u| is minimized (i.e., u=x), we'll have x/P = u/P = k/10 + 1/(10P), where k is either -3, -1, 1, or 3. Therefore |x|/P <= 3/10 + 1/(10P). Equivalently, |x| <= (3P + 1)/10.

Further, this inequality is strict at P=11, because at P=11 we have x=-1 and k=-1. The smallest P for which equality holds is P=13 (where x=4 and k=3).

Therefore the largest that |x|/P ever gets is 3/10 + 1/(10*13), because P=13 is the first prime for which we have k=3, and among those with k=3, the 1/(10P) term is largest when P is smallest (i.e., at P=13). Therefore, for all P, we also have |x|/P <= 3/10 + 1/130 = 4/13 < 1/3. This explains why in the above code we can initialize at i = P/3 rather than having to start at P/2.

Further, the bounds in the Usefulness section above can now be improved.

Lemma: Let N = 10c + d where c > 0 and 0 <= d <= 9. Then c + d|x| < N/10 + 9(3P + 1)/10. (Note the strict inequality.)

Proof of Lemma: by cases. Case I: d = 0, so N = 10c. Then c + d|x| = c = N/10 < N/10 + 9(3P + 1)/10.

Case II: 0 < d <= 9. Then 10c = N - d < N, so c < N/10. Therefore c + d|x| < N/10 + d|x| <= N/10 + 9|x| <= N/10 + 9(3P + 1)/10. QED.

Thus, if N > 3P (and N = 10c + d as before), then

3P + 1 <= N

9(3P + 1)/10 <= 9N/10

N/10 + 9(3P + 1)/10 <= N

c + d|x| < N/10 + 9(3P + 1)/10 <= N

So, if N > 3P then c + d|x| < N.

Therefore, we only have to find P, 2P and 3P, along with x. Given N > 0, while N > 3P, we replace N by |c + dx|, which decreases N. Eventually we'll get N <= 3P; at that point we stop and check whether N is equal to any of the numbers 0, P, 2P, or 3P.

We can't do better than 3P in general. For example suppose P = 13 and N = 39, so x = 4. Then replacing N by dx + c = 9(4) + 3 leaves N unchanged.

• Very nice explanation! You can save a byte by moving -1 outside the parenthesis: 43 bytes – fireflame241 Aug 20 '17 at 19:27
• @fireflame241 Thank you very much! I could claim that I left it at 44 just so I could cross it out (though this would be a lie). – mathmandan Aug 20 '17 at 20:19

## Whitespace, 92 bytes

Note that this language's syntax consists of only whitespace, so each whitespace character has been prefixed here with S, T, or L (corresponding to Space, Tab, and Linefeed, respectively). These can be removed without losing functionality, but they are included here in order to display it correctly.

S S S L
T   L
T   T   S S S L
T   T   T   S L
S S S S T   T   L
T   S S L
S L
T   S S S T S T L
T   S T T   S L
S T S S S S S S T   S T L
T   S S T   T   S T S S S S T   L
T   S S S S S S T   S T S L
T   S T S T L
S T L
L
L
.


Try it online!

# Japt, 14 bytes

Inspired by Neil's solution.

Ì*2%E-3 *UÄ /A


Test it online!

### Explanation:

  Ì  *2%E-3 *UÄ  /A
((UgJ*2%E-3)*U+1)/A
U                  // Implicit U = Input
gJ                // Get the char at index -1 (last char)
*2              // Multiply by 2
%E            // Mod 14
-3          // Minus 3
*U+1     // Multiply by U+1
/A  // Divided by 10


# Pyke, 10 bytes

~IIT*tR%)h


Try it here!

~I         -   Integers
I     )  -  filter(^, not v)
T*t     -    ^ *10 -1
R%   -   input % ^
h - ^[0]


# Excel, 27 bytes

=0.3/(MOD(A1,5)*2-5)*A1+0.1


Could be entered into Cell as

=.3/(MOD(A1,5)*2-5)*A1+.1


for 25 bytes, but Excel auto-updates.

• Actually I think you're allowed to claim the number of bytes you need to enter (but I'm too lazy to check meta). – Neil Sep 1 '17 at 9:37