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 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.
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.