Welcome to our community

Be a part of something great, join today!

Number Theory A result involving two primes I think is true.

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
Hello MHB.
There's a number theory problem I was solving and I can solve it if the following is true:

Let $p, q$ be distinct odd primes. Let $pk=q-1$ for some integer $k$. Then $p^k \not\equiv 1 \,(\mbox{mod } q)$.

I considered many such primes to find a counter example but failed. Can anyone see how to prove or disprove this?
 

CaptainBlack

Well-known member
Jan 26, 2012
890
Hello MHB.
There's a number theory problem I was solving and I can solve it if the following is true:

Let $p, q$ be distinct odd primes. Let $pk=q-1$ for some integer $k$. Then $p^k \not\equiv 1 \,(\mbox{mod } q)$.

I considered many such primes to find a counter example but failed. Can anyone see how to prove or disprove this?
\(q=31,\ p=5,\ k=6\)

\(p^k=15625=504\times 31+1\)

CB
 

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
\(q=31,\ p=5,\ k=6\)

\(p^k=15625=504\times 31+1\)

CB
Don't know if I should be happy or sad. This result was my best shot at the problem.
 

Deveno

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
perhaps you might post the actual problem you're trying to solve?
 

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
perhaps you might post the actual problem you're trying to solve?
Let $p$ be an odd prime. Show that there exists a prime $q$ such that $q \not |(x^p-p)$ for all integers $x$.
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
Let $p$ be an odd prime. Show that there exists a prime $q$ such that $q \not | (x^p - p)$ for all integers $x$.
The claim seems to holds true for prime $q = kp + 1$ for some $k \in \mathbb{N}$, $p > 3$, this progression is compatible with Dirichlet's Theorem thus $q$ is guaranteed to exist.
 
Last edited:

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
The claim seems to holds true for prime $q = kp + 1$ for some $k \in \mathbb{N}$, $p > 3$, this progression is compatible with Dirichlet's Theorem thus $q$ is guaranteed to exist.
That's exactly what I had in mind. My strategy didn't work though. See my first post in this thread. Do you have a way to make this work?
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
That's exactly what I had in mind. My strategy didn't work though. See my first post in this thread. Do you have a way to make this work?
Oh, wow, I apologise, the rearrangement in your first post threw me off. I don't have any idea right at the moment but I will think about it. It's an interesting problem.

EDIT: It seems the necessary condition is $p | q - 1$, so we just need an actual proof of that. But I still don't understand why it requires $p > 3$.
 
Last edited: