## Re: [PrimeNumbers] Love prime numbers; have a question

Expand Messages
• ... Welcome to the group! ... Well, when you pick your n, you have already picked your d. Because, as you stated in the above paragraph, n-1 = (d)2^s.
Message 1 of 3 , Nov 18, 2005
newjack56 wrote:
>
> Hello to all. I have recently been accepted to join this group(today
> actually)which makes my happy.

Welcome to the group!

> I would first like to thank the
> moderator(s) for allowing me to join. Before I requested to join, I
> read the last 20 messages posted and thought it would be good to
> introduce myself to the group and ask a question as well.
>
> My name is Matt Newshutz and I am a double-major senior at my city
> university(mathematics and education). I have always loved math, but
> when I was introduced to number theory on the collegiate level, my
> mind start to race full of ideas and wanting to better understand
> this or trying to prove that. In doing so, I am now writing my senior
> paper on Mersenne Primes and the Lucas-Lehmer Test. As much as I
> would love to try and pursue the ideas of proving theorems or
> conjectures that exist in the mathematics world and discuss these
> ideas amoung all iin the group, or create something entirely new, my
> spare time is mostly used for homework this semester(unfortunate, but
> needed).
>
> Anyhow, I have a question concerning Fermat's (little) Theorem and a-
> strong probability prime bases. It is stated that if n-1 = (d)2^s
> where d is odd and s is non-negative: n is a strong probable-prime
> base a (an a-SPRP) if either a^d = 1 (mod n) or (a^d)^2^r = -1 (mod
> n) for some non-negative r less than s. If I choose my n to by 5, a^d
> can be anything as long as it meets the 1 modulo n, so how exactly do
> you pick your a and d?? -Thanks for any help. -Matt

you stated in the above paragraph, n-1 = (d)2^s. Essentially what this
means is that you factor out all of the 2's from (n-1) and what you are
left with is an odd number, which here we call d. In the case of n=5,
n-1=4, so, when we've factored out all the 2's we get:
n-1 = (d)2^s
4 = (1)2^2
so in this example, d=1.
Now, in order to perform the a-SPRP test, you check first if:
a^d = 1 (mod n),
ie,
a^1 = 1 (mod 5) (this is only true of a=1 (mod 5) ie {1,6,11,...})
Now, if you chose "a" from {2,3,4} then we are looking for:
a^(d*2^r) = -1 (mod 5)
so, by example:
2^(1*2^0) = 2 (mod 5) [not what we're looking for]
2^(1*2^1) = -1 (mod 5) [this is what we're looking for]
so, 5 is a 2-SPRP
------------------------
3^(1*2^0) = 3 (mod 5) [not what we're looking for]
3^(1*2^1) = -1 (mod 5) [this is what we're looking for]
so, 5 is a 3-SPRP
------------------------
4^(1*2^0) = -1 (mod 5) [this is what we're looking for]
so, 5 is a 4-SPRP

Since n=5 is a prime anyway, we know that 5 is an a-SPRP for all values
of a. ie, All values of "a" that we test will verify that the number 5
is prime. This is a great test because it is easy to perform on
computers. However, it is not perfect. Sometimes, composite numbers
will be "reported as prime" by certain values of "a". Lets look at an
example and take n=2047=23*89
so n-1 = 2046 = 1023*2^1
so, if we take our "a" value to be 2,
to see if 2047 is a 2-SPRP, we first check:
2^1023 = 1 (mod 2047) [this is what we're looking for]
so, according to the test, 2047 is a 2-SPRP.

I can't remember if its a conjecture, or if its proven, but it is
believed (maybe proven) that there are an infinite number of composites
that are a-SPRP for every value of a. So, the test is not perfect, and
thats when we start looking at multiple values for "a". For example,
2047 is NOT a 3-SPRP. So, using a combination of 2 and 3 for our bases,
we can tell whether most numbers are prime or composite. However, there
are even exceptions to this rule. A man named Jaeschke did a lot of
research on using multiple bases and you can find his results in lots of
places on the web. Just google Jaeschke and sprp and you'll find lots
of great links. The first one returned by google is hosted by our
group's creator Chris Caldwell at:
http://primes.utm.edu/prove/prove2_3.html
Hopefully this is kind of what you were looking for. Again, welcome to
the group.

-David C.
Your message has been successfully submitted and would be delivered to recipients shortly.