Talk:Modular arithmetic

Template:Vital article

Division?

What about division? In arithmetic mod 13, 1/2 is 7 since 7*2=1. In arithmetic mod 10, 1/2 is impossible. With prime modulo, only n/0 is impossible. — Preceding unsigned comment added by 2A01:119F:2E9:2F00:94F9:AF78:6BF0:839F (talk) 16:59, 31 August 2016 (UTC)

Dividing one element a by another element b is defined for all a and nonzero b only when the integers modulo n constitute a field. — Anita5192 (talk) 18:15, 31 August 2016 (UTC)

This is true. Nevertheless, this article lacks of section "Modular operations", in which modular operations (modular addition, modular multiplication, modular exponentiation, modular inverse, and modular division) are defined and described. For the moment this is only partially done, and distributed in several sections. The fact that modular inverses may be computed by either extended Euclidean algorithm or Fermat's little theorem is lacking, although fundamental. Also fundamental and lacking are: the use of modular arithmetic for efficient linear algebra over the rationals, and the difficult problem of discrete modular logarithm. In other words, this article needs a complete rewriting. I intended to do that, but I have not yet get the time for doing this. D.Lazard (talk) 21:36, 31 August 2016 (UTC)

If b has a multiplive inverse mod n (b has a multiplive inverse mod n if and only if gcd(b,n)=1), then we can define (a/b) in arithmetic mod n, the definition is a × (the multiplive inverse of b mod n), e.g. in arithmetic mod 35, 1/2 is 18 and 1/3 is 12, but 1/5 is undefined, since 5 has no multiplive inverse mod 35. — Preceding unsigned comment added by 49.219.177.6 (talk) 11:03, 27 July 2018 (UTC)

Source code correct?

The source code in the page (reproduced below) allows values for m as large as 2^63 - 1, while simpler source codes usually require that m < 2^32, because of intermediate squaring operations involved that would overflow a 64-bits integer.

But...

I doubt that this source code is correct:

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
   uint64_t d = 0, mp2 = m >> 1;
   int i;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   for (i = 0; i < 64; ++i)
   {
       d = (d > mp2) ? (d << 1) - m : d << 1;
       if (a & 0x8000000000000000ULL)
           d += b;
       if (d > m) d -= m;
       a <<= 1;
   }
   return d;
}

Indeed, I translated it in C# as follows and I don't get correct results (tested against the BigInteger.ModPow(A, B, M) function provided in the .Net version 4):

public static UInt64 ModPow(UInt64 A, UInt64 B, UInt64 M)
{
    const UInt64 Mask = (UInt64)1 << 63; // 0x8000000000000000UL

    UInt64 D = 0;
    UInt64 MP2 = M >> 1;

    A %= M;
    B %= M;

    for (int i = 0; i < 64; i++)
    {
        D = (D > MP2) ? (D << 1) - M : D << 1;

        if ((A & Mask) != 0)
            D += B;

        if (D > M)
            D -= M;

        A <<= 1;
    }

    return D;
}

Can someone help? Otherwise the source code above should be removed from the page.

The source code below requires that M < 2^32, but at least it gives the correct result (tested against the BigInteger.ModPow(A, B, M) function):

public static UInt64 ModPow(UInt64 A, UInt64 B, UInt32 M)
{
    UInt64 R = 1;
    UInt64 C = A % M;

    while (B != 0)
    {
        UInt64 Bit = B & (UInt64)1;
        B >>= 1;

        if (Bit == 1)
        {
            R *= C;
            R %= M;
        }

        C *= C;
        C %= M;
    }

    return R;
}

Thanks. — Preceding unsigned comment added by Jp.basuyaux (talk • contribs) 12:26, 28 December 2016 (UTC)

I tested it out on C, and it appears to work for me.

This code here might be easier to understand, and the loop won't always run 64 iterations. It works for any uint64_t.

uint64_t mul_mod2(uint64_t a, uint64_t b, uint64_t m)
{
        uint64_t sum = 0;
        if (a >= m) a %= m;
        if (b >= m) b %= m;
        while (b) {
                if (b & 1) {
                        if (sum < m - a) // if (sum + a) < m
                                sum += a;
                        else
                                sum += a - m;
                }
                if (a < m - a) // if (a + a) < m
                        a += a;
                else    
                        a += a - m;
                b >>= 1;
        }
        return sum;
}

- Anonymous  — Preceding unsigned comment added by 69.147.212.194 (talk) 14:34, 21 September 2017 (UTC) 

Indeed it doesn't work. Copying and pasting both Anononymous' code and Wikipedia's article both fail with integers close to ULLONG_MAX of clmits, in particular (ULLONG_MAX-1)^2 modulo (ULLONG_MAX-82). It is better to just use the property: (a*b) mod m = (a-m)*(b-m) mod m. — Preceding unsigned comment added by 94.73.55.201 (talk) 19:59, 30 January 2019 (UTC)

Real numbers again

One cannot define full arithmetic (including multiplication) for the set S of real numbers modulo some positive real M.
However, one can define addition x+y and subtraction x−y (modulo M) for elements of S, and multiplication kx (modulo M) of an ordinary integer number k by a number x in S.
These operations are reasonably well behaved; if one defines the typical element of S as the class [x] = { x + i M : i in ℤ }, then [x] ± [y] = [x±y], and k[x] ⊆ [kx].
This artithmetic has many applications, such as computing with angles (M=2π), doing analysis and analytic geometry on a "flat torus" (T = S×S with M=1), computing atom distances in crystals (M = crystal cell size), etc..
The article should mention the fact that full modular arithmetic cannot be extended to reals; and there should be a separate article about this partial arithmetic.
--Jorge Stolfi (talk) 01:50, 14 April 2019 (UTC)

"Military" time

Isn't it kind of silly to refer to the 24-hour clock as "military" time since it's the standard timekeeping format in most of the world? Seems anglocentric and an unnecessary parenthetical.

2604:2D80:D686:1800:957E:4D42:301E:9A32 (talk) 02:23, 8 May 2020 (UTC)

Good point. I live in a county usually using 12-hour time and it still feels like an Americanism to me. I've reworded things for now, if anyone disagrees we can go to the third stage of WP:BRD. Alpha3031 (t • c) 07:21, 8 May 2020 (UTC)

Minus signs not rendering

@Vasily802:The first minus sign in the following equations in the Examples section does not seem to render properly.

${\begin{aligned}-8&\equiv 7{\pmod {5}}\\2&\equiv -3{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}$

I have seen this problem elsewhere from time to time on Wikipedia. An IP tried to fix it by inserting spaces, to no avail. I removed the spaces, because they did not help. The only thing that worked for me was to increase the magnification on my screen.—Anita5192 (talk) 04:54, 19 December 2020 (UTC)

This is happening in several articles. I just put in a help request at Wikipedia:Village pump (proposals)#Minus signs not rendering.—Anita5192 (talk) 17:16, 20 December 2020 (UTC)

Recently reverted text insertion

Hopefully, the following I added won't be reversed and deleted in future. If k a ≡ k b (mod n), then a ≡ b (mod ⁠n/gcd(k,n)⁠). Particularly, k is coprime with n, then gcd(k, n) = 1, and so a ≡ b (mod n).

Example 1. $x\equiv 7{\pmod {13}}$ and $k=2$, $\gcd(2,13)=1$ and so $2x\equiv 14{\pmod {13}}\equiv 1{\pmod {13}}\iff x\equiv {\frac {1}{2}}{\pmod {13}}$--Karho.Yau (talk) 15:56, 24 March 2022 (UTC)

This was reverted because it is too complicated to be useful in this article. In fact, it is too complicated for most people to verify. If you want to reinsert it, then first discuss it here and demonstrate why it is important.—Anita5192 (talk) 16:04, 24 March 2022 (UTC)

Primary topic discussion in progress for Modulo (disambiguation)

Hi all! I have started a discussion for the primary topic of Modulo (disambiguation), under the guise of a requested move, at Talk:Modulo (mathematics)#Requested move 28 December 2022. I don't propose to directly affect this page, but this page is listed upon that disambiguation page. Please visit the discussion there and contribute! Thanks —WT79 ^{(speak to | editing analysis | edit list)} 16:08, 28 December 2022 (UTC)

Does the glyph for congruence about a modulus have a name?

If not, I personally propose the “Threequals.” 2001:56A:FCFE:E200:C4EB:EB76:3964:B88F (talk) 07:51, 2 December 2023 (UTC)

Yes. The symbol is called the triple bar.—Anita5192 (talk) 13:57, 2 December 2023 (UTC)

Stupid name. Threequals is way better. 2001:56A:FCFE:E200:C09:49E7:BAD5:1973 (talk) 21:01, 2 December 2023 (UTC)