Jump to content

prime dilemma


moth

Recommended Posts

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.

primefolds.png

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

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 by wtf
Link to comment
Share on other sites

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

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.

Link to comment
Share on other sites

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

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
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.