prime number power residues and/or indices

John E. Franklin · 2012-01-18 10:08:49

I picked up a second-hand book today that
is filled with numbers about primes and their
indices and power residues.
I don't quite yet understand the preface that
tries to explain it.
It has something to do with using the mod(n) function,
which I think at least I get that much.
Here is some data from the book for the prime number 499:
#499:
power residues start off 1, 7, 49, 343 405 340 384 193 353 475
331 321 251 260 323 265 358 11 77 40
280 463 247 232 127 390 235 148 38 266 and
it goes on for 500 numbers!!!
The indices are different:
They start off with a blank for the 0th one.
Then they go 0, 435 447 372 208 384 1 309 396
145 17 321 429 436 157 246 421 333 91
82 448 452 47 258 416 366 345 373 212
and this continues for 499 of them.

The preface is kind of long, and so I won't try to
type anything about it here yet.

Anyone ever heard of these things before or have
any examples that are easy to understand for me?

anonimnystefy · 2012-01-18 10:22:59

hi John

just look it up on Wiki...oh wait,not that.

John E. Franklin · 2012-01-18 10:57:37

Drole (funny), I actually tried reading "primitive roots" (en francais wikipedia),
but didn't learn too much yet. The #499 actually has 498 indices and 498
power residues listed. Only the odd primes are listed. The number 2 is not there.
The preface mentions it only works for odd primes. Fermat himself is mentioned
as coming up with some of this stuff and then work was done on it for decades
after that. The book is from the 1960's.

bobbym · 2012-01-18 11:02:26

Beiler's book?

John E. Franklin · 2012-01-18 11:26:20

These are the only names I see:
H. S. Vandiver, Univ. of Texas, wrote the introduction.
C. A. Nicol, Univ. of Oklahoma and John L. Selfridge, Univ. of Washington designed the book, whatever that means.
And the numbers which constitute 95% of the book were
programmed by Lowry McKee, Univ. of Oklahoma.
The book is entitled:
A Table of Indices and Power Residues for all primes and prime powers below 2000.
under the direction of Richard V. Andree (chairman), also Univ of Oklahoma.
It's a 1962 book, Libary of Congress Catalog Card No. 62-8624.
It mentions that (3^12)-1 is divisible by 13. and a^(p-1) = 1(mod p), but
that is out of context as to when it is true, sorry.

bobbym · 2012-01-18 21:38:48

Hi John;

That formula is called Fermat's little theorem. He used it in his primality test.

John E. Franklin · 2012-01-19 01:25:03

Oh, thanks, I'll look up "primality test" or F-L theoreom unless you want to explain it. I'll tell you if I understand anything later...

John E. Franklin · 2012-01-19 02:31:51

See the Prime Numbers!!! thread now brought to the top in This is Cool as ZHero wanted to keep these matters in one place if possible.

John E. Franklin · 2012-01-19 02:48:17

So far I am relearning stuff (GCDivisor) (LCMultiple) (coprime) and some preliminary stuff like B/ezout's identity which I just drew a diagonal line and did some calculations with wikipedia. Interesting...

bobbym · 2012-01-19 03:14:51

Fermats little theorem is,

A generalization due to Euler is more useful for solving common test problems.

with GCD(a,n) = 1

For instance to find the last 2 digits of

we make use of the theorem to compute it. First GCD(100,7) =1 so we are looking for

so

7^11 = 1977326743

So the last two digits of 7^91 are 43.

John E. Franklin · 2012-01-19 03:30:02

Thanks bobby, I'm taking a hyotis. I think I gotta get a part-time job. Talk later. Gotta start saving money and make a move in ten years to Maine or some place a lot colder.

bobbym · 2012-01-19 03:39:47

A lot colder? I am trying to move to Florida where it is warmer!

John E. Franklin · 2012-01-21 00:09:14

Yep. Colder indeed, and preferably within an hour of some good hiking mountains. I'm half-Swedish, after all, and it predominates my blood. The Irish part seems to have diminished to the background. And the one American Indian they say, well, I don't know his or her past.
Well, I applied to many a part-time job, and even bought a pair of long pants for the winter!

bobbym · 2012-01-21 00:20:40

Mountain hiking? Sounds like mountain climbing.

John E. Franklin · 2012-01-21 06:52:42

Yes, but the angle is slighter and easier; no ropes ever needed, just
22 degrees slope or smaller, maybe 22.5 if you are really healthy!!
-22 to 0 to +22 degrees from the horizontal is nice hiking and still
has many beautiful views and vistas, and peaks.

bobbym · 2012-01-21 06:53:51

Oh, I get it. None of that in New Hampshire?

anonimnystefy · 2012-01-21 06:57:18

hi JEF

how're you today?

John E. Franklin · 2012-01-21 06:57:27

I figured out all the numbers in my power residue 1962 book computer generated on IBM 650-653.
I am surprised I finally figured out how to compute all the numbers, both the indices and the residues.
They are basically opposite sides of a hash table. Once you know that 73<-->530 for example, then you
know the indices (index) is just the opposite table 530 <--> 73. They might have been nice and told me
that in the preface, but oh, no. Leave the simple things in the dark!!

bobbym · 2012-01-21 06:59:06

Lots of books are like that. They assume too much. Or they just are too lazy.

John E. Franklin · 2012-01-21 06:59:39

Yes, New Hampshire's White Mountains are perfect climbing, and are the highest points of the Appalacian Trail from Georgia to Maine. But Vermont and Maine also have excellent hiking too. New Hampshire is probably best in the northern half, but I also will have to consider where I obtain a part-time job in ten years before I make the move.

bobbym · 2012-01-21 07:01:20

How is the property prices over there in Maine and Vermont?

John E. Franklin · 2012-01-21 07:05:13

For the prime number 151, the loop of power residue numbers is 150 long, as always, one shorter than the prime number.
The book starts with 3, not 2, only odd primes.
For the prime number 3, you always start with 1, then multiply (try 2) by 2 and see if it loops around with (3-1) numbers of 2 numbers in the loop. 1 times 2 is 2 and then 2 is less than 3 so 2 mod(3) is still 2. Then 2 times 2 continuing is 4, and that mod(3)'s back to 1 again, it's a continuous loop.
For the number 151, it worked for the number 2 also, but if it loops around too soon, I think you just try the next number up like 3, or 5, or 6, or 7, or 10, or 11, or 13, but I have a hunch you skip anything with double or triple factors in it like 2 times 2 times 3 or 3 times 3.

anonimnystefy · 2012-01-21 07:06:02

why are you ignoring me?

John E. Franklin · 2012-01-21 07:07:22

I haven't checked the prices, as I would be a renter, no doubt because I like to move every 2 to 4 years anyway for a change of scenery, and then renting provides easier moving without trying to sell. I don't need much space to live inside and I enjoy the outdoors quite often, so that is my first criteria of importance, the environment around where I live. Secondly, a nice view out a window is nice if possible, and low rent is utmost 2nd on the list actually.

John E. Franklin · 2012-01-21 07:08:24

I enjoy talking to everyone including you. I'm having a marvelous day, thanx for asking. I thought could be inferred from the stuff I've been working on successfully!

Math Is Fun Forum

#1 2012-01-18 10:08:49

prime number power residues and/or indices

#2 2012-01-18 10:22:59

Re: prime number power residues and/or indices

#3 2012-01-18 10:57:37

Re: prime number power residues and/or indices

#4 2012-01-18 11:02:26

Re: prime number power residues and/or indices

#5 2012-01-18 11:26:20

Re: prime number power residues and/or indices

#6 2012-01-18 21:38:48

Re: prime number power residues and/or indices

#7 2012-01-19 01:25:03

Re: prime number power residues and/or indices

#8 2012-01-19 02:31:51

Re: prime number power residues and/or indices

#9 2012-01-19 02:48:17

Re: prime number power residues and/or indices

#10 2012-01-19 03:14:51

Re: prime number power residues and/or indices

#11 2012-01-19 03:30:02

Re: prime number power residues and/or indices

#12 2012-01-19 03:39:47

Re: prime number power residues and/or indices

#13 2012-01-21 00:09:14

Re: prime number power residues and/or indices

#14 2012-01-21 00:20:40

Re: prime number power residues and/or indices

#15 2012-01-21 06:52:42

Re: prime number power residues and/or indices

#16 2012-01-21 06:53:51

Re: prime number power residues and/or indices

#17 2012-01-21 06:57:18

Re: prime number power residues and/or indices

#18 2012-01-21 06:57:27

Re: prime number power residues and/or indices

#19 2012-01-21 06:59:06

Re: prime number power residues and/or indices

#20 2012-01-21 06:59:39

Re: prime number power residues and/or indices

#21 2012-01-21 07:01:20

Re: prime number power residues and/or indices

#22 2012-01-21 07:05:13

Re: prime number power residues and/or indices

#23 2012-01-21 07:06:02

Re: prime number power residues and/or indices

#24 2012-01-21 07:07:22

Re: prime number power residues and/or indices

#25 2012-01-21 07:08:24

Re: prime number power residues and/or indices

Board footer