Register to reply

Automating Reduction by a Varying Modulus

by middleCmusic
Tags: automate, modulus, number theory, primality, reduce
Share this thread:
middleCmusic
#1
Mar1-13, 11:09 PM
P: 74
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.
Phys.Org News Partner Science news on Phys.org
'Smart material' chin strap harvests energy from chewing
King Richard III died painfully on battlefield
Capturing ancient Maya sites from both a rat's and a 'bat's eye view'
Mark44
#2
Mar2-13, 12:13 AM
Mentor
P: 21,397
Quote Quote by middleCmusic View Post
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).
I'm not following your logic here. In any case, 20/10 = 2 ##\equiv## 2 (mod 11). There's another way of checking for primes - the Sieve of Eratosthenes.
Quote Quote by middleCmusic View Post
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.
middleCmusic
#3
Mar2-13, 08:29 AM
P: 74
Oops my bad. That should have been a 2, yeah. The Sieve of Eratosthenes is not what I'm looking for though. I'm not expecting anyone to see my logic in doing this, just wondering if anyone knows how.


Register to reply

Related Discussions
Automating Email Opening Programming & Computer Science 2
Determine the modulus of elasticity, Poisson's ratio and the shear modulus. Introductory Physics Homework 1
Derive expressions for the transvers modulus and the longitudinal modulus of... Advanced Physics Homework 0
Spring Desing : How to Achive given shear modulus or modulus G and P(N) General Physics 0
Derive relationship between Young modulus and Shear modulus Introductory Physics Homework 0