prime dilemma

[moth]

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.

[wtf]

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

[moth]

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 ?

 

 

[wtf]

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

[moth]

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?

[wtf]

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.

[moth]

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. 

[amieparson]

Basically, any prime bigger than 3 always lands as 1 or 5 mod 6, and 1 or 2 mod 3. It’s like these numbers naturally follow a pattern, but as far as I know, they don’t have any special name because of it.

[Genady]

3 hours ago, amieparson said:

Basically, any prime bigger than 3 always lands as 1 or 5 mod 6, and 1 or 2 mod 3. It’s like these numbers naturally follow a pattern, but as far as I know, they don’t have any special name because of it.

They cannot land as anything else just by the fact that they are primes.

[KJW]

4 hours ago, Genady said:

They cannot land as anything else just by the fact that they are primes.

Actually, such numbers don't have to be prime, it is sufficient that they are not divisible by either 2 or 3. Also, 1 or 5 (mod 6) implies 1 or 2 (mod 3).

 

Edited November 19 by KJW

[sethoflagos]

4 hours ago, KJW said:

Actually, such numbers don't have to be prime, it is sufficient that they are not divisible by either 2 or 3. Also, 1 or 5 (mod 6) implies 1 or 2 (mod 3).

 

Consider the extensions:

N (mod 2) in [1]    (2 - 1) = 1 element (¹/2 of population)

N (mod 2*3) in [1, 5]    (2 - 1)*(3 - 1) = 2 elements (¹/₃ of population)

N (mod 2*3*5) in [1, 7, 11, 13, 17, 19, 23, 29]   (2 - 1)*(3 - 1)*(5 - 1) = 8 elements (⁴/₁₅ of population)

N (mod 2*3*5*7) in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]    (2 - 1)*(3 - 1)*(5 - 1)*(7 - 1) = 48 elements (⁸/₃₅ of population) 

ie we have successive screenings via Aristotle's sieve so they're neither definite primes nor non-primes. For want of a better term, I labelled them 'potential primes' back in the days when I dreamt of being able to solve the prime pairs conjecture.

Edited November 19 by sethoflagos
tidy up

[amieparson]

Basically, any prime bigger than 3 always lands as 1 or 5 mod 6, and 1 or 2 mod 3. It’s like these numbers naturally follow a pattern, but as far as I know, they don’t have any special name because of it.
It reminds me of messing around with numbers when I usually roll d20 and noticing certain outcomes show up more often in specific situations—it feels random at first but actually has its own logic. Modular math is kind of like that.