I_love_tigersugar's blog

By I_love_tigersugar, 10 years ago, In English

In number theory, we always write a ≡ b (mod p) means that the reminder of division of a by p and the reminder of b by p are the same. Today, I have a question about this definition.

1. Same reminder of integers:

If , a ≡ b (mod p) means or . It's quite easy to see that.

2. Same reminder of rational numbers:

We also write , for example: . What do they mean?

The above definition is obviously wrong, since . But with the modular multiplicative inverse, can be written as a * b - 1 ≡ r (mod p). So, in this case, I think the definition should be: means: For every pair of integers (A, B) satisfies , we always have . Note that so we can use the definition for integers.

3. Same reminder of irrational numbers:

In the editorial of problem 446C - DZY Loves Fibonacci Numbers, the authors wrote:

Fn ≡ 276601605(691504013n - 308495997n) (mod 109 + 9)

The correctness of the last equation can be proved easily. However, to get the final equation, we need some transform like: .

My question is, how can we define equations a ≡ b (mod p), when a or b is irretional number like that, and why the above transform is correct.

I'm looking forward to hearing your responses. Thank you for your help!

P/s: I know, this blog may have something difficult to be understood, but please do not vote down it. I have thought a lot about this problem, but I can't find the answer.

  • Vote: I like it
  • +30
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

5^0.5 is a square root of x^2 = 5 (mod 1e9+9), you can calc it by wolframalpha.

»
10 years ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

means a and b are the same value on ring "Integers modulo p" (Zp)

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    From Wikipedia: For a positive integer n, two integers a and b are said to be congruent modulo n, and written as

    a ≡ b (mod n)

    if their difference a − b is an integer multiple of n (or n divides a − b).

    How do you think about this?

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 10   Vote: I like it 0 Vote: I do not like it

      That's the same thing. (with addition) is defined as the group of integers modulo the subgroup generated by n, namely . And we have

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The above definition is only right in case a and b are integers. We can't use it in more general case.

»
10 years ago, # |
  Vote: I like it +26 Vote: I do not like it

I don't think it's possible or important to extend the definition of modulo on all irrational numbers. For example, how could you calculate π modulo 41?
Nevertheless, there is a useful technique called finding of discrete root. Its definition is quite simple.

Let's begin from the very beginning. Why can one divide the numbers modulo m? The result can be not an integer. Though if we invent a good definition for division modulo m, it will help us a lot further.

Let's make it this way: if . One can simply look that such a definition doesn't take us out of integers and has all the properties normal division has.

What about the square (or some other) root? Let's make a definition: if .

Now you can use the definition above to find the integer roots modulo m. For example, you can check this property for 383008016 you mentioned in post.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It would be consistent to define the equivalence class of π in this scenario as , although the question remains whether that is actually a useful tool to have. As far as finding a representative in the range [0, 41) is concerned, the fmod function provides an implementation

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also your definition of a square root cannot really work like that. It assumes that there is only one such a, but that might not the case, e.g.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      The thing is that every integer number that satisfies our definition should also satisfy all our requirements. This is some quality measure of a good definition.

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        So you're defining as a set? That is however inconsistent with the definition for real numbers, where it is a concrete value (the positive one that fulfills the condition).

        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          In fact, every number according to modular arithmetic is a set of numbers. 1 modulo 41 is a set of {...-81,-40,1,42,83...}. And yes, this really differs the modular arithmetic from the common one.

          But I think one should not be feared of the sets of numbers when every number from such set has a property essential for us.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I agree with you that we don't need to make definition of modulo on all irrational numbers. But if we write a ≡ b (mod p) with some irrational number a, we should make definition about it.

    Your definition for is ok. So how can you define the (I saw it in the editoral).

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Recursively.

      As now we can find the square root modulo m and we already know how to add modulo m we take some a which is and add 1 modulo m.

      In fact, this works the same as in common math. When you first knew one can find square roots of every non-negative number you simultaneously knew that the result of the operation can be used in addition, subtraction etc.

  • »
    »
    10 years ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    I've been thinking about that exact editorial for quite a while and planned on writing the same question in a blog myself. You seem to know some about modular arithmetics so I hope you can answer me those two questions:

    1) We can properly divide by modulo when it is prime, as otherwise the multiplicative inverse may not be unique and dividing is not really useful.

    In the same way, to define sqrt(5) = 383 008 016 , does it mean that this is the only number which squared gives 5 modulo 10^9+9.

    2) Edit: Ops, I guess I misread the editorial.

    Thanks in advance! :)

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      1/ You should notice that, the number of x satisfies x2 ≡ b (mod p) is usually even, as x2 ≡ (p - x)2 (mod p). However, we can define as: for every x satisfies x2 ≡ a (mod p), we always have x ≡ b (mod p) or x ≡ p - b (mod p). With this definition, is correct. (And I think that's why the problem uses modulo 109 + 9 instead of 109 + 7 :D).

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        So are you saying that if we had used 616991993 instead, the answer would still be correct? I find that really counterintuitive :D

        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Ask your intuition a simple question: will the fibonacci formula become wrong if we take another number as — especially, , as it also gives 5 when squared.

          And then check the result manually :)

          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            That's a very nice way to put it, thanks a lot :)