Talk:Modular arithmetic
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. 
Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · NYT · WP Library 
Archives: Index, 1, 2 
Modular arithmetic has been listed as a level4 vital article in Mathematics. If you can improve it, please do. This article has been rated as BClass. 
WikiProject Mathematics  (Rated Bclass, Toppriority)  


Index 1, 2 

Sections older than 12 months may be automatically archived by Lowercase sigmabot III. 
Division?[edit]
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?[edit]
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 64bits 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_MAX1)^2 modulo (ULLONG_MAX82). It is better to just use the property: (a*b) mod m = (am)*(bm) mod m. — Preceding unsigned comment added by 94.73.55.201 (talk) 19:59, 30 January 2019 (UTC)
Real numbers again[edit]
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[edit]
Isn't it kind of silly to refer to the 24hour 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 12hour 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[edit]
@Vasily802:The first minus sign in the following equations in the Examples section does not seem to render properly.
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[edit]
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. and , and so Karho.Yau (talk) 15:56, 24 March 2022 (UTC)