Modular arithmetic, similar to Fermat's little theorem.

Question

kainui · Answer

Is it possible to find some integer $a$ for primes $p$ and $q$ so that: $1 < a < q$ and: $$p^a \equiv p \mod q$$

ganeshie8 · Answer

aren't you asking for the multiplicative order of $p$ ? 

this is always possible when $p$ is not a generator of the cyclic group <q>

kainui · Answer

I see, I guess I am asking that I didn't know! Hmm so is there any kind of simple way I might know about relationships between primes and generators? I was thinking as long as p and q are both prime, then p would always be a generator for q but I am now not sure where I got this idea from.

ganeshie8 · Answer

generators are primitive roots, not every other prime is a primitive root of  a particular prime right ?

ganeshie8 · Answer

consider $q = 5$

kainui · Answer

Beats me, I suppose if p<q would that make it a primitive root? I am not sure what it would require for this to happen.

When q=5 I think p=2 or p=3 are both generators I'm thinking about 7 but that also is a generator I'm not sure is there a specific counter example you're thinking about?

kainui · Answer

Oh I am foolish about that last comment I just need to find some prime that's congruent to 1 mod 5 like 31 and that will be a counter example.

ganeshie8 · Answer

yea $q = 5$ has no solutions for
$$p^a \equiv p \pmod q ,~~a\lt q$$

ganeshie8 · Answer

lets try $q=7$

ganeshie8 · Answer

$$2^4 \equiv 2 \pmod 7 ,~~4\lt 7$$

the multiplicative order of $2$ is $4-1$

ganeshie8 · Answer

I guess your question refers to the distribution of primitive roots

kainui · Answer

Yeah in reality I was looking to see if this was divisible by q:

$$1+p+p^2+\cdots + p^{q-1} \mod q$$

And I had thought erroneously by Fermat's little theorem that this meant p was a generator of q and rewrote it as:

$$1+2+3+\cdots + (q-1) \mod q$$
$$\frac{q(q-1)}{2} \equiv 0 \mod q$$

Sadly this is not true because of what you've just told me

kainui · Answer

I'm trying to help my friend who wants to prove this conjecture: https://en.wikipedia.org/wiki/Feit%E2%80%93Thompson_conjecture Anyways haha this was my failed attempt but maybe you will find it fun at least or have some suggestions.

ganeshie8 · Answer

I see... yeah that sum is divisible by q when p is a primitive root of q

ganeshie8 · Answer

but that may not be a necessary condition

there might be some other cases where that sum is divisible by q eventhough p is not a primitive root of q

kainui · Answer

Thanks yeah, I guess it might be worth it to just sorta continue on "assuming p is a generator of q" and try to at least patch up some of the proof for when it's not later. Might be able to get infinitely many cases ruled out at the very least which narrows it down a hair and might end up being extended later.