[Question]
  [
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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), 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
```
  
[Answer]
## JavaScript (ES6), ~~32~~ ~~25~~ 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
[Answer]
# [Python 2](https://docs.python.org/2/), 27 bytes
```
lambda n:(n%5*2-5^2)*n/10+1
```
[Try it online!](https://tio.run/##LY7BboMwEETP2a/YSyWSkNa7tjGOxJ9UrUBtFCTiokAV9evpGOLL7JsZ2zv@zdefpMuleV@G9tZ9tZzORXrxBz35D90f0puYoyyPaz98s5xpNzX39vHZp/F3Lva0S2XX3Nqx6NNcTq/TOPSw4Y93ONw1zaVI@5JTydvQLSLMJyGxzI4kADxJZFZSWIEUsyWbW5Cci5DL6MihIZbc6jryGSvyuFFRlSuQnKmhkDFQQEWVAio11Rk81YBIcS1GEiN4zEAtW@xlAj5WaGR8LNjTYk/Nbo2tc9kizQdRFiF9YvXEuJ4tNbQRLm7DPw "Python 2 – 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]`.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~10~~ 8 bytes
```
,N⁵æiAÞḢ
```
[Try it online!](https://tio.run/##y0rNyan8/1/H71Hj1sPLMh0Pz3u4Y9H///8NDUDAGAA "Jelly – Try It Online")
### Explanations
```
,N       Get [Input, -Input].
⁵æi      Modular inverse of 10 mod each of [Input, -Input].
AÞ       Sort by absolute value.
Ḣ        First.
```
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 14 bytes
```
∧.ℤ≜×₁₀-₁;?%0∧
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/r//1HHcr1HLUsedc45PP1RU@OjpgZdIGVtr2oAlPn/39DI/H8UAA "Brachylog – Try It Online")
[Answer]
# [Python 2](https://docs.python.org/2/), 69 54 53 bytes
**Edit:** -15 bytes thanks to [@Mr.Xcoder](https://codegolf.stackexchange.com/users/59487/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!](https://tio.run/##HY/BDoMgEETP7VfsxURbTEFRxMT@SNMDjTEladEYD/Tr6SwHdnbfkFnYfsd7DU1Ky/Rx39fsyIk41WosXaHkJV7dTcmqAA4zLaUTdazLeJdVte4U04LqyQd6KCVItTgGxwpq0DfQFrwF01ANptF30A5eD9ZjNlADZsAG6AC1nCM5VHKqzCO4yksaHtu8MndsaC4ds45Zz/c4XZn8LHYHdm0uzPIOa5/j@bTtPhzkBf7oq/QH)
[Answer]
# [Python 2](https://docs.python.org/2/), ~~31 29~~ 27 bytes
```
lambda n:3/(n%5*2-5)*n/10+1
```
[Try it online!](https://tio.run/##K6gsycjPM/qfZhvzPycxNyklUSHPylhfI0/VVMtI11RTK0/f0EDb8H9BUWZeiUKahqGhpg6QNAaT5mDSEkQaGWv@BwA "Python 2 – Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt), ~~16~~ 9 bytes
*Saved way too many bytes thanks to an observation by @xnor*
```
_*AÉ vU}c
```
[Test it online!](https://ethproductions.github.io/japt/?v=1.4.5&code=XypBySB2VX1j&input=MTAwMDAwMw==) 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
```
[Answer]
# Java 8, ~~23~~ 21 bytes
```
n->3/(n%5*2-5)*++n/10
```
Port of [*@Neil*'s JavaScript (ES6) answer](https://codegolf.stackexchange.com/a/139698/52210), but -2 bytes thanks to *@Nevay* due to implicit flooring of integers.
[Try it here.](https://tio.run/##jVLBjoIwFLz7Fe9iUjQgUBGJ2f2D9eLReKgFTRUfRKrJxvDtWNCrGV/aJn2dzkybOam78qu64FN@7nSpmob@lOHHiMiwLa4HpQta99uhQVr0K3sr12nddKOxyhpNa2L6oY79XzkTPE4msZ94k@mUZ1HYrV7Q@rYvHfR9416ZnC5OTWzs1fBxuyPlvaQ2/40tLkF1s0HtjmzJggMtosgblD8DJAKkCJABQIwkYsQg0SskMjlHDHPEkCCTCySxQBIpYkjRT6bI5BIxLBFDBvMQwsyFMHQhshHh4MbQqcRO@4L5/Q6VDYW@d6i3r3bUdk8)
[Answer]
# Excel, 25 bytes
```
=.3/(MOD(A1,5)*2-5)*A1+.1
```
(Excel corrects to: 
```
=0.3/(MOD(A1,5)*2-5)*A1+0.1
```
)
[Answer]
# [Pyke](https://github.com/muddyfish/PYKE), 12 bytes
```
3Q5%}5-f*hTf
```
[Try it here!](http://pyke.catbus.co.uk/?code=3Q5%25%7D5-f%2ahTf&input=17&warnings=0)
[Answer]
# [Pyth](https://pyth.readthedocs.io), 14 bytes
```
h/*x-y%QK5K2QT
```
**[Try it here.](http://pyth.herokuapp.com/?code=h%2F%2ax-y%25QK5K2QT&test_suite=1&test_suite_input=11%0A13%0A17&debug=0)**
[Answer]
# [Pyke](https://github.com/muddyfish/PYKE), 10 bytes
```
~IIT*tR%)h
```
[Try it here!](http://pyke.catbus.co.uk/?code=%7EIIT%2atR%25%29h&input=11&warnings=0)
```
~I         -   Integers
  I     )  -  filter(^, not v)
   T*t     -    ^ *10 -1
      R%   -   input % ^
         h - ^[0]
```
[Answer]
# [Python 2](https://docs.python.org/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!](https://tio.run/##K6gsycjPM/r/P8A2M6@gtERD0zrTNkDfmKs8IzMnVSFTy9BANUDX0CpT19aQq6AoM69EIfP/f0swMAQA "Python 2 – 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](https://en.wikipedia.org/wiki/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.
[Answer]
## [Whitespace](http://web.archive.org/web/20150623025348/http://compsoc.dur.ac.uk/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!](https://tio.run/##K8/ILEktLkhMTv3/X0FBgYuTi5MTTAMpLiBDgRMoAuQrgEgFTgUQDywF4sJFQEJgATAHKg7SApIGIi6u//8NDQE)
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 14 bytes
*Inspired by [Neil's solution](https://codegolf.stackexchange.com/a/139698/61613).*
```
Ì*2%E-3 *UÄ /A
```
[Test it online!](https://ethproductions.github.io/japt/?v=1.4.5&code=zCoyJUUtMyAqVcQgL0E=&input=OTk5OTk5MQ==)
### 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 
```
[Answer]
# [Husk](https://github.com/barbuz/Husk), 10 bytes
```
ḟȯ¦⁰←*10İ±
```
[Try it online!](https://tio.run/##FcwhDsJAEEbh@5An9u@0nc45kARPQgiCEHQRaG6Aw1JcdYPgGvQiy9Y9873d@bTPh@NlzXzt8298fF/Tc@6H@XZfKX2G6Z1z3kjIkKOgMqrAhDm1qI3aaYwmaEXruHDDg87ogigqFZ/KIC0daJlVpU3bPw "Husk – Try It Online") A port of [ETHproductions' answer](https://codegolf.stackexchange.com/a/139694).
]