Algorithm to add two digits to the end of a number to calculate a specific modulus?

Question

So, lets say I have a number 123456. 123456 % 97 = 72. How can I determine what two digits need to be added to the end of 123456 such that the new number % 97 = 1? Note--it must always be two digits.

For example, 12345676 % 97 = 1. In this case, I need to add the digits "76" to the end of the number.

(This is for IBAN number calculation.)

Answer 1

x = 123456

x = x * 100
newX = x + 1 + 97 - (x % 97)

Edit: put the 100 in the wrong place

Answer 2

This is the equation that that you need

 X = Y -(Number*100 mod y) - 1

where:

   Number = 123456
    Y = 97
    X the number you need

Answer 3

You calc the modulo of 12345600 to 97 and add (97 - that + 1) to that number. So you get what RoBorg explained whay cleaner above :)

Answer 4

Modulo arithmetic is really not that different from regular arithmetic. The key to solving the kind of problem that you're having is to realize that what you would normally do to solve that problem is still valid (in what follows, any mention of number means integer number):

Say you have

15 + x = 20

The way that you solve this is by realizing that the inverse of 15 under regular addition is -15 then you can write (exploiting commutativity and associativity as we naturally do)

15 + x + (-15) = (15 + (-15)) + x = 0 + x = x = 20 + (-15) = 5

so that your answer is x = 5

Now on to your problem.

Say that N and M are known, and you're looking for x under addition modulo k:

( N + x ) mod k = M

First realize that

( N + x ) mod k = ( ( N mod k ) + ( x mod k ) ) mod k

and for the problem to make sense

M mod k = M

and

x mod k = x

so that by letting

N mod k = N_k

and

( a + b ) mod k = a +_k b

you have

N_k +_k x = M

which means that what you need is the inverse of N_k under +_k. This is actually pretty simple because the inverse under +_k is whatever satisfies this equation:

N_k +_k ("-N_k") = 0

which is actually pretty simple because for a number y such that 0 <= y < k

(y + (k - y)) mod k = k mod k = 0

so that

"-N_k" = (k-N_k)

and then

N_k +_k x +_k "-N_k" = N_k +_k "-N_k" +_k x = 0 +_k x = x = M +_k "-N_k" = M +_k ( k - N_k )

so that the solution to

( N + x ) mod k = M

is

x = ( M + ( k - ( N mod k ) ) ) mod k

and for your problem in particular

( 12345600 + x ) % 97 = 1

is solved by

x = ( 1 + ( 97 - ( 12345600 mod 97 ) ) ) mod 97 = 76

Do notice that the requirement that you solution always have two digits is built in as long as k < 100