>

Welcome to the group!

> Hello to all. I have recently been accepted to join this group(today

> actually)which makes my happy.

> I would first like to thank the

Well, when you pick your n, you have already picked your d. Because, as

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