We have $\left(\frac{x+1}{x} \right)^p \equiv 1 \pmod q$ (since $x, x+1$ are relatively prime). Thus by FLT and orders, we must have $p | q-1,$ implying the result.

shiningsunnyday wrote: We have $(\frac{x+1}{x})^p \equiv 1 \pmod q$ (since $x, x+1$ are relatively prime). Thus by FLT, we must have $p | q-1,$ implying the result. It's also needed to prove that if $q \equiv 1 \pmod p$ then such $x$ exists. (anyways, it's an easy question)

bgn wrote: Let $p,q$ be prime numbers ($q$ is odd). Prove that there exists an integer $x$ such that: $$q |(x+1)^p-x^p$$If and only if $$q \equiv 1 \pmod p$$ First prove that {$1^p,2^p,...,(q-1)^p$}={$1,2,...,q-1$} (mod $q$) if and only if $(q-1,p)=1$ and then prove that if $p|q-1$ then there exist $x,x+a$ such that $x^p\equiv (x+a)^p$ (mod $q$) so $(xa^*)^p\equiv (xa^*+1)^p$ (mod $q$) and so done:)

Let $q=pk+1$. Let $y$ be a primitive root of $q$ so $y^{q-1}\equiv 1\pmod q$. Let $a=y^k$ and note that $a^{p}\equiv 1\pmod q$. Also note that $gcd(a-1,q)=gcd(y^k-1,q)=1$ since $y$ is a primitive root of $q$ and $k<q-1$. So there exists an integer $x$ (for example $x=(a-1)^{q-2}$) such that $x(a-1)\equiv 1\pmod q$ or $xa\equiv x+1\pmod q$ or $(x+1)^p\equiv (xa)^p\equiv x^p\pmod q$.

I have a solution

Huf wrote: Let g be a prime root of q. And a=q-1/p Choose b Wich g^b +1 =g^a (mod q) Now let c =P-1 - b So (g^a)^p = 1 (mod q) Then (g^b + 1 ) ^ p = 1 (mod q) So g^c = x X^p .(g^b + 1 )^p = x^p mod q So X is answer.

bgn wrote: Let $p,q$ be prime numbers ($q$ is odd). Prove that there exists an integer $x$ such that: $$q |(x+1)^p-x^p$$If and only if $$q \equiv 1 \pmod p$$ Only if part: There exists a n such that, $(x+1)^p-x^p \equiv 0(mod q)$it implies that,$(\frac{x+1}{x})^p \equiv 1 (mod q)$ On the other hand by FLT, $(\frac{x+1}{x})^{q-1}\equiv 1 (mod q)$ So now it is easy to see that, P fully divides q-1 or q-1 fully divides p. The last one is impossible because q-1 is a prime number because it happens p must be 2 which is impossible and p would be greater that p. So, p fully divides (q-1) and the proof of this part is done

bgn wrote: Let $p,q$ be prime numbers ($q$ is odd). Prove that there exists an integer $x$ such that: $$q |(x+1)^p-x^p$$If and only if $$q \equiv 1 \pmod p$$ Using Euler's theorem we've $q \mid (x+1)^{\phi(q)}-x^{\phi(q)}=(x+1)^{q-1} -x^{q-1}$ for $x \neq q^r, (q^{r}-1)$, for some $r \in \mathbb{Z}^{+}$ then from the given result we've $q \mid (x+1)^p -x^p$ From these we get $q \mid (x+1)^{\gcd (p,q-1)} -x^{\gcd (p,q-1)}$ Then we note that if $\gcd (p,q-1)=1$ then we end up with $q \mid 1$ which is a contradiction , therefore it follows that $\gcd(p, q-1) >1$ ,then as $p$ is a prime it follows that $p \mid q -1 \Leftrightarrow q \equiv 1\,(mod\, p)$ as desired $\blacksquare$

Hope this works The case when $p=2$ can be dealt with separately. If $q \mid (x+1)^p-x^p$, then $ \left (\frac{x+1}{x} \right)^p \equiv{1} \pmod{q}$. Therefore the order (name it $o$) divides $p$ and $q-1$. Now it cannot be $1$ because then $x^{-1} \equiv{0} \pmod{q}$. Therefore, it must be $p$, and as a result, $p \mid q-1$. For the other direction let $g$ be the primitive root of $q$. I claim that $x=(g^{\frac{q-1}{p}}-1)^{-1}$ works. First we prove that it exists. Suppose not. Then we have $g^{\frac{q-1}{p}} \equiv{1} \pmod{q}$, contradicting the whole definition of primitive roots . Now notice that $$ \left (\frac{x+1}{x} \right)^p \equiv{(x^{-1}+1)^p} \equiv{(g^\frac{q-1}{p})}^p \equiv{g^{q-1}} \equiv{1} \pmod{q}$$and we are done.

We have, $$((x+1)\cdot x^{-1})^p\equiv 1 \pmod q$$Let $Ord_q((x+1)\cdot x^{-1})=d$. Since, $d\vert q-1$ and $d\vert p$. So, $d\vert \gcd(p,q-1)$ which is either $1$ or $p$. If $d=1$, then $x+1\equiv x \pmod q$ which would give $q=1$ but $q$ is a prime. So, $\gcd(p,q-1)=p\implies q\equiv 1\pmod p$ $\blacksquare$

Did no one use the fact that if $d\mid p-1$, then there exists an integer $e$ that has $\mathrm{ord}_{p}(e)=d$? We can check that $q\nmid x$, so $q$ is coprime to $x$. Suppose that $q\mid (x+1)^p-x^p$. This is equivalent to $(\tfrac{x+1}{x})^p\equiv 1\pmod{q}$, so $\mathrm{ord}_q(\tfrac{x+1}{x})\mid p$. If $\mathrm{ord}_q(\tfrac{x+1}{x})=1$, then $x+1\equiv x\pmod{q}$, contradiction, so $\mathrm{ord}_q(\tfrac{x+1}{x})=p$. Then since $(\tfrac{x+1}{x})^{q-1}\equiv 1\pmod{q}$ by Fermat's Little Theorem, we have $p\mid q-1$, so the "only if" direction is true. Now suppose that $p\mid q-1$. We know from this assumption that there exists some positive integer $e$ such that $\mathrm{ord}_q(e)=p$. Note that $e\not\equiv 1\pmod{q}$, since $\mathrm{ord}_q(1)=1$. Thus we can take $x\equiv (e-1)^{-1}\pmod{q}$ (motivated by realizing that $(x+1)^p\equiv x^p\pmod{q}$ is equivalent to $(1+x^{-1})^p\equiv 1\pmod{q}$). We have $$\frac{(x+1)^p}{x^p}\equiv \left(\frac{(e-1)^{-1}+1}{(e-1)^{-1}}\right)^p\equiv (1+(e-1))^p=e^p\equiv 1 \pmod{q},$$so $(x+1)^p\equiv x^p\pmod{q}$ and the "if" direction holds as well. Hence we are done.

The modular equation can be rearranged to say that $t^p \equiv 1(mod \ q)$ for some prime $p$ less than $q$ and integral $t$. Now order of $t$ modulo $q$ divides $p$ so it can be $1$ or $p$. If it is $1$ then we get that $q$ divides $1$ which is impossible. Hence order is $q$ and due to FLT it must divide $q-1$ which gives the desired. For the converse condition, we need to prove there exists an integer $k$ such that $k^p$ is $1$ modulo $q$ where $p$ is a prime dividing $q-1$, however if $g$ is a primitive root of $q$, then order of $g^k$ is $\frac{q-1}{gcd(q-1,k)}$ so simply choose $k=p$ and we are done.

Denote by $x^{-1}$ the inverse modulo of $x$. So having $q\mid (x+1)^{p}-x^p$ is equivalent to $(x+1)^p\equiv x^p\pmod{q}$, so it is clear that $x$ is coprime with $q$ (if you want try $x\equiv 0\pmod{q}$ and you'll get a contradiction) So multiplying both sides by $(x^{-1})^p$ gets us $(1+x^{-1})^p\equiv 1\pmod{q}$. Let $\sigma $ be the multiplicative order of $1+x^{-1}$ modulo $q$ so we get : $\sigma\mid p$, hence $\sigma =p$ or $\sigma =1$, but considering $\sigma =1$ we get $x^{-1}\equiv 0\pmod{q}$ which is impossible as $x^{-1}$ and $q$ are coprime. So $\sigma =p$. By Fermat Little Theorem we have $\sigma \mid q-1$ i.e $p\mid q-1$.

storage