MHB A result involving two primes I think is true.

  • Thread starter Thread starter caffeinemachine
  • Start date Start date
  • Tags Tags
    Primes
AI Thread Summary
The discussion centers on a number theory problem involving distinct odd primes p and q, specifically the assertion that if pk = q - 1 for some integer k, then p^k is not congruent to 1 modulo q. A participant attempts to find a counterexample but fails, sharing an example with p = 5, q = 31, and k = 6, which supports the claim. The conversation shifts to a related problem about the existence of a prime q such that q does not divide (x^p - p) for all integers x, with a suggestion that primes of the form kp + 1 may satisfy this condition. The necessity of p being greater than 3 is questioned, indicating a need for further proof and understanding of the conditions involved. The thread highlights the complexity and interrelated nature of these number theory problems.
caffeinemachine
Gold Member
MHB
Messages
799
Reaction score
15
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?
 
Mathematics news on Phys.org
caffeinemachine said:
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
 
CaptainBlack said:
\(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.
 
perhaps you might post the actual problem you're trying to solve?
 
Deveno said:
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$.
 
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:
Bacterius said:
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?
 
caffeinemachine said:
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:
Back
Top