- #1
middleCmusic
- 74
- 0
Hey guys,
I'm doing some experimenting recently with some primality tests, and I need help figuring out how to automate the following:
Given an even number N, divide by 2k ([itex]k \in \mathbb{N}[/itex]).
If N/2k is an integer, reduce mod 2k+1.
(If N/2k is not an integer, simply move on to the next one.)
Do this for all 2k ≤ N/2.
Then print those k (or 2k, doesn't really matter to me) for which the resulting reduction by the modulus 2k+1 is odd.
EX: N = 20. 20/2 [itex]\equiv[/itex] 1 (mod 3). 20/4 [itex]\equiv[/itex] 0 (mod 5). 20/6 non-integer. 20/8 non-integer. 20/10 [itex]\equiv[/itex] 10 (mod 11).
Print: 2k = 2 (or k = 1), since this is the only odd reduction that was obtained.
If it helps, I have Mathematica and Maple, as well as some basic understanding of LaTeX, but my programming skills are pretty crappy. Thanks in advance!
P. S. I wasn't sure if I should post this in the Computer Science forum, but I figured that it's more of a math topic anyway, and there are bound to be some math people who know how to do this.
I'm doing some experimenting recently with some primality tests, and I need help figuring out how to automate the following:
Given an even number N, divide by 2k ([itex]k \in \mathbb{N}[/itex]).
If N/2k is an integer, reduce mod 2k+1.
(If N/2k is not an integer, simply move on to the next one.)
Do this for all 2k ≤ N/2.
Then print those k (or 2k, doesn't really matter to me) for which the resulting reduction by the modulus 2k+1 is odd.
EX: N = 20. 20/2 [itex]\equiv[/itex] 1 (mod 3). 20/4 [itex]\equiv[/itex] 0 (mod 5). 20/6 non-integer. 20/8 non-integer. 20/10 [itex]\equiv[/itex] 10 (mod 11).
Print: 2k = 2 (or k = 1), since this is the only odd reduction that was obtained.
If it helps, I have Mathematica and Maple, as well as some basic understanding of LaTeX, but my programming skills are pretty crappy. Thanks in advance!
P. S. I wasn't sure if I should post this in the Computer Science forum, but I figured that it's more of a math topic anyway, and there are bound to be some math people who know how to do this.