Automating Reduction by a Varying Modulus

middleCmusic

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.

Mark44

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.

middleCmusic

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.