# Number TheoryA result involving two primes I think is true.

#### caffeinemachine

##### Well-known member
MHB Math Scholar
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
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
$$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
perhaps you might post the actual problem you're trying to solve?

#### caffeinemachine

##### Well-known member
MHB Math Scholar
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
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
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
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: