moth Posted July 13, 2021 Share Posted July 13, 2021 For any prime number n > 3, n mod 6 = 1 or 5. any prime number n > 3, n mod 3 = 1 or 2. The same prime numbers are in column 1 either way and the primes from column 2 (mod 3) are in column 5 (mod 6). Are there 2 kinds of prime numbers? Is there a name for these primes? The attached png is the primes mod 2,3,6, and 7. Link to comment Share on other sites More sharing options...

wtf Posted July 13, 2021 Share Posted July 13, 2021 38 minutes ago, moth said: For any prime number n > 3, n mod 6 = 1 or 5. any prime number n > 3, n mod 3 = 1 or 2. The same prime numbers are in column 1 either way and the primes from column 2 (mod 3) are in column 5 (mod 6). Are there 2 kinds of prime numbers? Is there a name for these primes? I don't think they have names, but there's a famous theorem of Fermat that says an odd prime is the sum of two squares if and only if p = 1 (mod 4). https://en.wikipedia.org/wiki/Fermat's_theorem_on_sums_of_two_squares 1 Link to comment Share on other sites More sharing options...

moth Posted July 13, 2021 Author Share Posted July 13, 2021 Thanks for the link. Found some good stuff in the "see also" section too. Now I think I'm misusing the term "Mod". The '%' operator in C is the remainder from integer division, is the result of that operation the same as the mod operation ? Link to comment Share on other sites More sharing options...

wtf Posted July 13, 2021 Share Posted July 13, 2021 (edited) 58 minutes ago, moth said: Thanks for the link. Found some good stuff in the "see also" section too. Now I think I'm misusing the term "Mod". The '%' operator in C is the remainder from integer division, is the result of that operation the same as the mod operation ? Great question. Yes they are "the same but a little different." In math, mod is an equivalence relation on the integers. We say that [math]a \equiv b \pmod n [/math] for two integers [math]a, b[/math] if it happens to be the case that [math]n | a - b[/math], where the vertical bar means "divides." So for example [math]5 \equiv 3 \pmod 2[/math] and [math]17 \equiv 5 \mod 3[/math]. You can verify that this is an equivalence relation: It's reflexive, symmetric, and transitive. It partitions the integers into [math]n[/math] pairwise-disjoint equivalence classes. It's a fundamental concept in number theory. In programming languages, mod is a binary operator that inputs two integers and outputs a third: 5 % 3 = 2. It inputs 5 and 3, and outputs the remainder when 5 is integer-divided by 3. The math and programming concepts are closely related. [math]a % n[/math] is the remainder when [math]a[/math] is integer-divided by [math]n[/math]; that is, the result of [math]a % n[/math] is the smallest positive element of the equivalence class of [math]a[/math] under the [math]\pmod n[/math] equivalence relation. This turns out to be the same as the remainder under integer division. The tl;dr is that in math, mod is an equivalence relation that inputs a pair of numbers and a modulus and returns True or False; whereas in programming, mod is a binary operator that inputs an integer and a modulus and outputs the smallest positive member of the equivalence class of the integer mod the modulus. The difference is shown by, say, the fact that [math]17 \equiv 14 \pmod 3[/math]; but [math]17 \ \% \ 3 = 2[/math] and not [math]14[/math]. That is. even though mathematically [math]17 \equiv 14 \pmod 3[/math], in a programming language, [math]17 \ \% \ 3 == 14[/math] would evaluate to False. That's an example that illustrates the difference. Edited July 13, 2021 by wtf Link to comment Share on other sites More sharing options...

moth Posted July 14, 2021 Author Share Posted July 14, 2021 I think I see the difference now. 5 and 3 (and all odd numbers?) are equivalent mod 2 so the mod operator returns 'true' while the '%' operator returns the same value (1) for (any odd number) mod 2, but the '%' operator would take a few iterations to determine if two integers are in the same equivalence set? Link to comment Share on other sites More sharing options...

wtf Posted July 14, 2021 Share Posted July 14, 2021 51 minutes ago, moth said: I think I see the difference now. 5 and 3 (and all odd numbers?) are equivalent mod 2 so the mod operator returns 'true' while the '%' operator returns the same value (1) for (any odd number) mod 2, Yes exactly. 51 minutes ago, moth said: but the '%' operator would take a few iterations to determine if two integers are in the same equivalence set? I suppose you'd have to subtract the two integers and see if the result is integer-divisible by the modulus. That seems like the most sensible way. Probably not the only way. 1 Link to comment Share on other sites More sharing options...

moth Posted July 14, 2021 Author Share Posted July 14, 2021 Thanks for clearing that up. @wtf. Reading the Wikipedia page about equivalence classes now. In the pdf i attached, each column is an equivalence class for mod 2, 3, 6, and 5. Link to comment Share on other sites More sharing options...

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now