Talk:Modular arithmetic

Skip to table of contents

This is the talk page for discussing improvements to the Modular arithmetic article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Archives: Index, 1, 2: 12 months

Archives

Index 1, 2

Archive 1 — congruency symbols; notation; clock arithmetic; modulo in computer science (discussion leading to the creation of the modulo operation article); usage in check digits; misc.

This page has archives. Sections older than 365 days may be automatically archived by when more than 10 sections are present.

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

"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)[reply]

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)[reply]

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)[reply]

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)[reply]

Recently reverted text insertion

Hopefully, the following I added won't be reversed and deleted in future. If $k a \equiv k b (mod n)$ , then $a ≡ b (mod .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠n/gcd(k,n)⁠)$ . Particularly, $k$ is coprime with $n$ , then $gcd(k, n) = 1$ , and so $a \equiv 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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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

Some use "equivalent to," although I suppose this may be colloquial in usage. 67.170.223.108 (talk) 06:27, 15 April 2024 (UTC)[reply]

user:D.Lazard rejects modulus 1

user:D.Lazard rejects the modulus 1 with the argument: "1 is never used as a modulus, and extending the definition to would make nonsensical some of the listed basic properties listed below".

I agree that the change does not carry much of a fluidum. But it is correct and even useful at least e.g. for certain generic theorems.

And I could not find one(¬1) basic property listed in the article which becomes nonsensical. I asked him to show me one, if not all, of the listed basic properties which become nonsensical.

However, I would add a statement to the paragraph "Integers modulo n" telling that

  $\mathbb {Z} /1\mathbb {Z} =\mathbb {Z} /1=\mathbb {Z} _{1}=\{0\}$

is the 1-elementic trivial group.

Nomen4Omen (talk) 08:25, 4 February 2024 (UTC)[reply]

Nomen4Omen changed

n>1

into

n\geq 1

in the definition given in the first line of § Congruence, with the edit summary "the trivial modulus 1 is anyway a modulus". This sounds as WP:OR as no evidence is provided that 1 is considered as a possible modulus in standard textbooks. Also, such a change requires to verify that all properties listed in the article remain correct after the change. This has clearly not been done, as one of the properties begins with "If c ≡ d (mod φ(n)), where φ is Euler's totient function, ...". This sentence is wrong with both definitions, as it implies a congruence modulo 1 when n = 2 and modulo 0 when n = 1.

       Another terrible mistake of D.Lazard: φ(1) = 1 (and ≠ 0, see Euler's totient function)

So the change does not improve the article, although the first line of the section requires some attention.

As congruences modulo 0 and 1 are commonly considered (even in this article), it seems that 0 and 1 are rarely considered as moduli. So I suggest to change the beginning of the section into Given a nonnegative integer

n

, two integers

a

and

b

are said to be congruent modulo

n

, if there is an integer

k

such that

a \equiv b (mod n)

. This is denoted

a \equiv b (mod n)

. If

n > 1

, it is called a modulus.

Clearly, such a change would require an update of the article for testing when

n < 2

must be explicitly excluded. (This is implicily excluded when

n

is supposed to be prime or composite.)

By the way, the integers modulo 1 are more than the "1-elementic trivial group". They form the zero ring. I'll ass this to the article. D.Lazard (talk) 11:26, 4 February 2024 (UTC)[reply]

Two sources cited in the article define congruence for n any positive integer.^[1]^[2]—Anita5192 (talk) 16:20, 4 February 2024 (UTC)[reply]

I agree that congruences may and should be defined modulo any nonnegative integer, but this does implies that 0 and 1 may be called moduli. This is the motivation of the above suggested formulation. D.Lazard (talk) 19:24, 4 February 2024 (UTC)[reply]

User:D.Lazard mixes up "0 and 1" as moduli — and does not realize that 0 really never is a modulus, whereas 1 may happen to be. -Nomen4Omen (talk) 10:22, 5 February 2024 (UTC)[reply]

WP:personal attacks about my supposed understanding of mathematics are not an argument in this discussion. On the opposite, they weaken your position. Please remove them. If you remove the preceding post I would agree that you remove also my answer. D.Lazard (talk) 18:50, 5 February 2024 (UTC)[reply]

Clearer — and critics wrt. User:D.Lazard's emotions removed. -Nomen4Omen (talk) 19:13, 5 February 2024 (UTC)[reply]

References

^ Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd ed.). Lexington: D. C. Heath and Company. p. 76. LCCN 77171950.
^ Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. p. 87. ISBN 9780132683005. LCCN 71081766.

Disambiguation with Modulo

@D.Lazard, The purpose of the hatnote {{About}} is to clearly distinguish between closely-related articles so the reader knows where to go, not to perfectly define the topic of the article.

The current definition "about computation modulo a fixed integer" does not clearly distinguish the articles. First, "modulo" is not a common-language word outside of mathematics. Second, both articles are meaningfully about computation.

The clearest difference between these two at a glance is either (a) that one involves an equivalence relation, while the other is a function, or (b) the notation used: "a (mod m)" or "mod(a,m)"

Unless you or someone else has a better idea, the "about" hatnote should be reverted back to one of these. But in any case, the current description is not helpful to the average reader and needs to be changed. Farkle Griffen (talk) 22:39, 18 December 2024 (UTC)[reply]

[1] Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd ed.). Lexington: D. C. Heath and Company. p. 76. LCCN 77171950.

[2] Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. p. 87. ISBN 9780132683005. LCCN 71081766.

[1]

[2]