Finding the value based on the value of the remainder

[Vital]

Homework Statement

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.

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

The Attempt at a Solution

[/B]
(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!

 

[Buffu]

How can I find both k and y?

You can't.

If you want to solve

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

for y then choose a random value for k in

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

and solve for y.

 

[Vital]

You can't.

If you want to solvefor y then choose a random value for k inand solve for y.

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

 

[Buffu]

I have an initial expression,

can you show me that ?

First it was (116 – 97 + 8) % 26 + 97 = x, so x = 98

Which operator is % ?

 

[Vital]

can you show me that ?Which operator is % ?

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

 

[SammyS]

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

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

You seem to be asking:

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

 

[Vital]

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

You seem to be asking:

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

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.

 

[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?

 

[SammyS]

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.

Once again: I can get as far as k x 26 + 1 = y - 97 + 8, which boils down to k × 26 + 90 = y
Two unknowns here.

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.

 

[Vital]

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.

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]?

 

[SammyS]

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]?

Yes.

 

[Vital]

Yes.

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

 

[SammyS]

Homework Equations

The initial equation:
(y − z + i) mod m = x − z

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

 

[Vital]

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

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

 

[SammyS]

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

OK.

You have been using m = 26 . Also, you wanted y to be in some specific range of values.

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]?

It will be more efficient to lead you through some specific case, then try to get a more general approach.

 

[Vital]

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.

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

 

[SammyS]

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 de-crypt them; and the algorithm I need to compute is for this decryption stage.

(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.
Added in Edit:

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​

?

 

[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

(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.
Added in Edit:

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

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

"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​

?

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?

 

[haruspex]

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

How can I find both k and y?

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?

 

[Vital]

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?

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

 

[haruspex]

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

Ok, and you have

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

So what is the range for k$\times$26?

 

[Vital]

Ok, and you have

So what is the range for k$\times$26?

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.

 

[haruspex]

y -78

Yes.

- 87

No.

it looks horrible mathematically

No, it simplifies trivially.

 

[Vital]

Yes.

No.

No, it simplifies trivially.

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.

 

[haruspex]

hence k×26 shall have the range ( [97,122] - 78 )

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

 

[Vital]

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

The only thing I see is k = ( [97,122] - 78 ) / 26
But what is the exact value of y, namely that value in the range [97,122]?

 

[haruspex]

The only thing I see is k = ( [97,122] - 78 ) / 26
But what is the exact value of y, namely that value in the range [97,122]?

If x+78 is in the range [97, 122], what is the smallest possible value of x? What is the largest?

 

[Vital]

If x+78 is in the range [97, 122], what is the smallest possible value of x? What is the largest?

The smallest x = 19 and the largest x = 44

 

[haruspex]

The smallest x = 19 and the largest x = 44

Right, so what is the range for 26k? What values of k fit?

 

[Vital]

Right, so what is the range for 26k? What values of k fit?

Well... [19/26 , 44/26] (I am not reducing the second value yet)
I don't yet see where you are guiding me to, but I am really curious, and all in hope :)

 

[haruspex]

Well... [19/26 , 44/26]

Isn't k an integer?
Edit:
@Vital, what integers are in that range?

 

[SammyS]

Let's look at the initial equation again.

We have (y − 97 + i) mod 26 = x − 97

For encrypting, you start with a y value such that 97 ≤ y ≤ 122 .

This gives 0 ≤ (y − 97) ≤ 25 .

To this we add i, then perform the mod 26 operation so that values of x fall into the same range of values as do values of y.

Specifically, 0 ≤ (x − 97) ≤ 25 and thus 97 ≤ x ≤ 122 .

So you could say that it's that i value which which makes inverting this expression a bit tricky.

The quantity, (y − 97 + i), falls in the range of values, [ i , 25 + i ] .

The mod 26 operation preserves any of these values falling in the [ 0 , 25 ] interval. Any other values are put into the [ 0 , 25 ] interval, by adding or subtracting appropriate multiples of 26.

Consider the following idea:

If you were to subtract i from (y − 97 + i), then of course you have (y − 97)

Similarly, if you subtract i from (x − 97). that gives (x − 97 − i). The values for this fall in the interval [ −i , 25 − i ]. Applying the mod 26 operation to this should give the result you need to obtain (y − 97) .
.

 

[Vital]

Let's look at the initial equation again.

We have (y − 97 + i) mod 26 = x − 97

For encrypting, you start with a y value such that 97 ≤ y ≤ 122 .

This gives 0 ≤ (y − 97) ≤ 25 .

To this we add i, then perform the mod 26 operation so that values of x fall into the same range of values as do values of y.

Specifically, 0 ≤ (x − 97) ≤ 25 and thus 97 ≤ x ≤ 122 .

So you could say that it's that i value which which makes inverting this expression a bit tricky.

The quantity, (y − 97 + i), falls in the range of values, [ i , 25 + i ] .

The mod 26 operation preserves any of these values falling in the [ 0 , 25 ] interval. Any other values are put into the [ 0 , 25 ] interval, by adding or subtracting appropriate multiples of 26.

Consider the following idea:

If you were to subtract i from (y − 97 + i), then of course you have (y − 97)

Similarly, if you subtract i from (x − 97). that gives (x − 97 − i). The values for this fall in the interval [ −i , 25 − i ]. Applying the mod 26 operation to this should give the result you need to obtain (y − 97) .
.

Unfortunately, no. If I understood you correctly, then the expression should be:
(x - 97 - i)%26 + 97 = y
But this is the expression I came up with a week ago, when I tried to solve the problem. It doesn't work, and produces an inappropriate result.

 

[SammyS]

Unfortunately, no. If I understood you correctly, then the expression should be:
(x – 97 – i)%26 + 97 = y
But this is the expression I came up with a week ago, when I tried to solve the problem. It doesn't work, and produces an inappropriate result.

If the % operator does indeed give the remainder,then that should give correct results.

Try this on your test cases.

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

Use: y = (x – 97 – i)%26 + 97

(1): x = 116, i = 17, should give y = 99 .

y = [(116 – 97 – 17)%26] + 97 = [ 2 % 26] + 97 = 2 + 97 = 99​

(2) x = 98, i = 20, should give y = 104

y = [(98 – 97 – 20)%26] + 97 = [ (–19) % 26] + 97 = 7 + 97 = 104​

(3) x = 97, i = 18, should give y = 105

y = [(97 – 97 – 18)%26] + 97 = [ (–18) % 26] + 97 = 8 + 97 = 105​

It appears to work just fine.

 

[Vital]

If the % operator does indeed give the remainder,then that should give correct results.

Try this on your test cases.

Use: y = (x – 97 – i)%26 + 97

(1): x = 116, i = 17, should give y = 99 .

y = [(116 – 97 – 17)%26] + 97 = [ 2 % 26] + 97 = 2 + 97 = 99​

(2) x = 98, i = 20, should give y = 104

y = [(98 – 97 – 20)%26] + 97 = [ (–19) % 26] + 97 = 7 + 97 = 104​

(3) x = 97, i = 18, should give y = 105

y = [(97 – 97 – 18)%26] + 97 = [ (–18) % 26] + 97 = 8 + 97 = 105​

It appears to work just fine.

Yes, I thought so also when I initially came up with this same equation, so I thought that my math is completely incorrect, and I started asking for help, because the program doesn't compute it this way somehow, and I get completely different results. Well, maybe it's some problem with computing the remainder when the quotient is negative. It might be the case. I have to investigate that further.
Thank you so much for your huge patience and your help!