# Homework Help: Finding the value based on the value of the remainder

Tags:
1. May 30, 2017

### Vital

1. The problem statement, all variables and given/known data
Hello!
Please, help me to learn how to solve the following task - I really have no idea how to do that. What's important is that I need an algorithm that I can apply to the equation with different values.

2. Relevant equations
The initial equation:
(y - z + i) mod m = x - z

Meaning that the value of (x - z) is the value of the remainder after dividing (y - z + i) by m.
Let me show one example with numbers, so it will be clear what I am asking about.

3. The attempt at a solution

(y - 97 + 20) mod 26 = 98 - 97

According to the definition: a mod b = c, and a=c+kb

Therefore in my example:

c = 98 - 97 (I am not computing this difference on purpose, because it is important for me to see all values involved)
a = (y - 97 + 20)
b = 26
k is unknown, but also y is unknown, so I have two unknowns here.
Proceeding further I get:

k×26+98−97=y−97+20

How can I find both k and y? Is there a general algorithm for such equations?
I will be very grateful for your help and explanation - I need to learn this.
Thank you very much!

2. May 30, 2017

### Buffu

You can't.

If you want to solve
for y then choose a random value for k in
and solve for y.

3. May 30, 2017

### Vital

Oh, this is so sad. You see I have an initial expression, in which y is known, but x is unknown; and then I need to do the reverse operation, in which x is now known and y is not.
Given my previous example:
First it was (116 – 97 + 8) mod 26 + 97 = x, so x = 98
But in the next round I know x, which is 98, but I don't know y, and I need to find it, and it has to become 116, so I need to find the way to get back to 116.
The second expression I need to solve: (y – 97 + 8) mod 26 + 97 = 98
I hope my explanation didn't sound too awfully cluttered. :)

Last edited: May 30, 2017
4. May 30, 2017

### Buffu

can you show me that ?
Which operator is % ?

5. May 30, 2017

### Vital

I am sorry - I have edited my post to substitute % for mod. % comes from the programming language.

6. May 30, 2017

### SammyS

Staff Emeritus
For this example, you have chosen y=116, and as a result, x is 98 .

Can we recover the value of y from the following?
(y – 97 + 8) mod 26 + 97 = 98​

Of course that can be restated as, "We need to find y such that (y – 97 + 8) mod 26 =1 ."

What does this tell you about possible values for (y – 97 + 8), which is the same as (y – 89) ?

7. May 30, 2017

### Vital

Yes, this is exactly what I need to find. And I have no idea how to solve these equations. As I have posted in my original post there are two unknowns.
Once again: I can get as far as k x 26 + 1 = y - 97 + 8, which boils down to k x 26 + 90 = y
Two unknowns here.
So I am looking for the algorithm to solve this type of equations:
(y - z + i) mod m = x - z
y - z + i = k x m + (x - z)
where y is the value I am interested in and it is unknown, and k is unknown; all other values are given.

8. May 30, 2017

### phinds

How much is 22 mod 3?
How much is 61 mod 3?
How much is 334 mod 3?

Do you begin to see the problem?

9. May 30, 2017

### SammyS

Staff Emeritus
One more step to say
k × 26 = y – 90
In words, that is: y – 90 is some multiple of 26.

Therefore, there is no single value of y which will work. There are many values which solve this. Each results from a different value of k, and k must be an integer.

In the case of y = 116, this requires that k = 1.

If k = –3, we have y = 12.

10. May 30, 2017

### Vital

I am starting to see the problem. Do you think an algorithm can be found if I know that my values of y have to be strictly between [97, 122]?

11. May 30, 2017

### SammyS

Staff Emeritus
Yes.

12. May 30, 2017

### Vital

Can you help me, please? I am very weak at math yet.

13. May 30, 2017

### SammyS

Staff Emeritus
Assuming that the above is the general equation, which of those have some fixed value?

14. May 30, 2017

### Vital

Only z, it is always 97; all other values change in each consecutive equation, but they are all known except for y (and k, which is a partial quotient, and it is not shown in the above equation).

15. May 30, 2017

### SammyS

Staff Emeritus
OK.

You have been using m = 26 . Also, you wanted y to be in some specific range of values.
It will be more efficient to lead you through some specific case, then try to get a more general approach.

16. May 30, 2017

### Vital

Sorry! Yes, 26 and 97 are fixed. All other values change.
I can write a few equations, which are part of a larger set; the set can be of any size, that is why I need to create a general algorithm - I am learning programming, and have written a tiny program, which encrypts letters in the text, and then it have to decrypt them; and the algorithm I need to compute is for this decryption stage.

Let's say I have 3 initial equations:

(1) (99 – 97 + 17) mod 26 + 97 = x; x = 116
(2) (104 – 97 + 20) mod 26 + 97 = x; x = 98
(3) (105 – 97 + 18) mod 26 + 97 = x; x = 97

The next step is to do the reverse, namely finding Y:
(1) (Y – 97 + 17) mod 26 + 97 = 116
(2) (Y – 97 + 20) mod 26 + 97 = 98
(3) (Y – 97 + 18) mod 26 + 97 = 97

17. May 30, 2017

### SammyS

Staff Emeritus
(y − 97 + i) mod 26 = x − 97

OK. That helps a lot.

You appear to be doing a very basic encryption in which each letter of the alphabet is assigned a value (code) from 0 through 25. It looks like the letter to be given the code 0 is determined by the variable, i. The rest follow in alphabetical order, with letter a getting the code equal to one more than the code for letter z.
Actually the 0 - 25 code is the quantity (x − 97), the right hand side. So the "code letter" represented by x is also an ASCII character, rather than being a number in the range 0 - 25..

"Why the 97?", you may ask. 97 is the ASCII code for the (lower case) letter 'a'.

What is this "mod" function?

"n mod m" is the remainder that results from dividing n by m .

So,
what is the meaning of
(y − 97 + i) mod 26​
?

Last edited: May 30, 2017
18. May 30, 2017

### Vital

No, it is much easier. I have written this equation because it allows me to wrap around the set of alphabetical characters - by taking the remainder of 26 I just make sure I don't get beyond these 26 letters. But I am fine with the code, I just need to figure out the reverse math. :-)

Yes, of course, 97 is the ASCII code for 'a' - I won't wonder as I wrote that myself. :-)

As to your last question about the meaning: well, I have showed it above in previous messages, that (y − 97 + i) mod 26 gives the remainder, and of dividing (y − 97 + i) by 26, hence the expression is:
(y − 97 + i) / 26 = K x 26 + [(y − 97 + i) mod 26], where K is the partial quotient. How do I find y and K?

19. May 31, 2017

### haruspex

Suppose you had a solution pair. Consider adding 1 to k. What would you have to do to y to make a second solution pair?

You need another constraint, the allowed range of y, perhaps?

20. May 31, 2017

### Vital

I have a constraint on values of y, and I have showed them above. From 97 to 122 including.

21. May 31, 2017

### haruspex

Ok, and you have
So what is the range for k$\times$26?

22. May 31, 2017

### Vital

In this specific case (with these values):
k×26 = y -78, hence k×26 shall have the range ( [97,122] - 87 ), though it looks horrible mathematically.
k×26 equals some number between 97 and 122, inclusive, minus 87.

23. May 31, 2017

### haruspex

Yes.
No.
No, it simplifies trivially.

24. May 31, 2017

### Vital

That was a typo: 78
k×26 = y -78, hence k×26 shall have the range ( [97,122] - 78 ).
k×26 equals some number between 97 and 122, inclusive, minus 78.

25. May 31, 2017

### haruspex

Yes, but can't you see how to simplify that immediately?