Prime numbers and divisibility related problem 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?
 A: 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$.
A: 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)
