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

[caffeinemachine]

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]

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]

\(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]

perhaps you might post the actual problem you're trying to solve?

 

[caffeinemachine]

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]

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.

 

[caffeinemachine]

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]

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