1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding the value based on the value of the remainder

Tags:
  1. May 30, 2017 #1
    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. jcsd
  3. May 30, 2017 #2
    You can't.

    If you want to solve
    for y then choose a random value for k in
    and solve for y.
     
  4. May 30, 2017 #3
    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
  5. May 30, 2017 #4
    can you show me that ?
    Which operator is % ?
     
  6. May 30, 2017 #5
    I am sorry - I have edited my post to substitute % for mod. % comes from the programming language.
     
  7. May 30, 2017 #6

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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) ?
     
  8. May 30, 2017 #7
    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.
     
  9. May 30, 2017 #8

    phinds

    User Avatar
    Gold Member
    2016 Award

    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?
     
  10. May 30, 2017 #9

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  11. May 30, 2017 #10
    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]?
     
  12. May 30, 2017 #11

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Yes.
     
  13. May 30, 2017 #12
    Can you help me, please? I am very weak at math yet.
     
  14. May 30, 2017 #13

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Assuming that the above is the general equation, which of those have some fixed value?
     
  15. May 30, 2017 #14
    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).
     
  16. May 30, 2017 #15

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  17. May 30, 2017 #16
    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
     
  18. May 30, 2017 #17

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    (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​
    ?
     
    Last edited: May 30, 2017
  19. May 30, 2017 #18
    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?
     
  20. May 31, 2017 #19

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
  21. May 31, 2017 #20
    I have a constraint on values of y, and I have showed them above. From 97 to 122 including.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Finding the value based on the value of the remainder
  1. Find value (Replies: 9)

  2. Finding value (Replies: 22)

Loading...