Prime numbers and divisibility related problem

Question

If $p, q$ are primes such that $p\nmid (n-1)$, but $p \mid (n^q-1)$, then show that $q \mid p-1$.

My approach:

Given $p \nmid n-1$, but $p \mid (n^q-1)$ implies $p \mid (n^{q-1}+n^{q-2}+...+n+1)$
Say $ (n^{q-1}+n^{q-2}+...+n+1)= kp$. Now if we assume, $p \mid n$, it forces to have $p \mid 1$, implying $p=1$. Then our proof is obviously complete.

If $p \nmid n$, then from Fermat's theorem, we have: $$ n^{p-1}=1+k_1p$$

So, again, in the question it is given that $$n^{q}=1+k_2p$$ Let us assume there exists some $x$ such that $n^{x}=1+k_3p \Rightarrow k_3p=(n-1) (n^{x-1}+n^{x-2}+...+n+1)$ . Again $p \nmid (n-1)$ implies $p \mid (n^{x-1}+n^{x-2}+...+n+1)$

if $x<q$, we have $$ (n^{q-1}+n^{q-2}+...+n+1)= kp$$ $$\Rightarrow (n^{q-1}+n^{q-2}+...+n^x)+(n^{x-1}+n^{x-2}+...+n+1)=kp$$

Now $p \mid (n^{x-1}+n^{x-2}+...+n+1)$ implies, $p \mid (n^{q-1}+n^{q-2}+...+n^x)$, which is not possible as $p \nmid n$ and $p \mid (n^{q-1}+n^{q-2}+...+n+1)$

If $x>q$

We have $$ n^{x-1}+n^{x-2}+...+n+1= k_3p$$ $$ \Rightarrow (n^{x-1}+n^{x-2}+...+n^q)+(n^{q-1}+n^{q-2}+...+n+1)= k_3p$$ $$ \Rightarrow (n^{x-1}+n^{x-2}+...+n^q)=k_4p$$

Again $p \nmid n$ and $p \mid (n^{q-1}+n^{q-2}+...+n+1)$ force to have $x$ is a multiple of $q$.

If we take $x=p-1$, our proof is complete.

Is it correct?

Answer 1

Let $r$ be minimal among all natural numbers $k$ such that $$n^k\equiv 1\pmod{p}$$ The number $r$ is usually called order of $n$ modulo $p$.

---

Lemma If $n^s\equiv 1\pmod{p}$ then $r\mid s$.

Proof Write $s=l\cdot r+o$ where $o$ is remainder when $s$ is divided by $r$, so $0\leq o<r$. Then we have $$1\equiv n^s\equiv (n^r)^l\cdot n^o \equiv n^o \pmod p$$ If $o>0$ then we have smaller number than $r$ such that $n^o\equiv 1\pmod{p}$ thus $o=0$.

---

Back to the problem: Since $n^q\equiv 1\pmod p$ thus by lemma $r\mid q$. So $r=1$ or $r=q$. But $r$ can not be $1$, since if $r=1$ we get $p\mid n-1$ which is not true. So $r=q$.

Now by Fermat little theorem we have $n^{p-1}\equiv 1\pmod{p}$, so by lemma we have also $r\mid p-1$ and thus $q\mid p-1$.

Answer 2

I don't think so.

Now $p \mid (n^{x-1}+n^{x-2}+...+n+1)$ implies, $p \mid (n^{q-1}+n^{q-2}+...+n^x)$, which is not possible as $p \nmid n$ and $p \mid (n^{q-1}+n^{q-2}+...+n+1)$

doesn't seem correct - why is there a contradiction?

(unless I'm missing something obvious which is entirely possible)

Hint (if you want one):

Consider making $x$ minimal and see if you can work stuff out about $x$

Solution (if you want one):

Take $x$ to be minimal such that $p|n^x-1$ For any $y$ such that $p|n^y-1$, let $y=qx+r$ where $q,r$ are integers and $0\leq r<x$ The cool thing is, $p|n^{qx}-1$ because $n^x-1$ is a factor. Therefore $$p|(n^{qx+r}-1)-(n^{qx}-1),n^{qx+r}-n^{qx},n^{qx}(n^kr-1)$$ But since $r<x$, and $x$ was minimal, we know that $r=1$ which means that $x|y$.

Last piece (if you're still stuck):

Therefore $x|q,p-1$ so $x|\gcd(q,p-1)$ but this gcd divides $q$. If the gcd is $1$, then that means by definition of $x$, $p|n^1-1$ which is silly. Otherwise, $\gcd(q,p-1)=q$ so $q|p-1$ as required.

(The solution is very similar to what you've written so I'm not 100% sure that your solution is wrong, but like I said, I can't see the contradiction in that step I quoted above)