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.)

Solution 1

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 :)

Solution 2

x = 123456

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

Edit: put the 100 in the wrong place

Solution 3

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

Solution 4

Let’s say we have to receive the number containing 12 digits.

Step 1: Write any random number of 10 digits, i.e. 2 digits less than needed, e.g. 1234567890 – this is X

Step 2: X * 100 = 123456789000. ‘123456789000’ - this is Y

Step 3: Y / 97 = '1272750402.061856'. '06' – this is Z

Step 4: 97 – Z + 1 = 92. '92' – this is W

Step 5: Final Deal Number is X followed by W, i.e. '123456789092'

Examples of accepted numbers: 100000000093 100000000190 100000000287 Etc.

Solution 5

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

View more solutions

Comments

[Ken Gentle]

123456 + 1 + 97 - ((123 456 * 100) % 97) = 123532 The answer should be 12345676, right?

[Ken Gentle]

And the parenthesis ')' are unbalanced - three closing, two opening. Is there a tern missing?

[Jim]

I think I get it--two digits = newX - x. I think you need to add that to your answer.

[Lee Meador]

How come you say - 1 and all the other answers have + 1? Are you missing some parentheses?