Can $1+kq$ divide $p^3$ for distinct primes $p$ and $q$ with $p^3\not\equiv 1\pmod{q}$

70 Views Asked by At

If $p^2-1$ is not divisible by $q$, i.e., $p^2\not \equiv 1 \pmod{q}$, but $1+kq$ divides $p^2$, where $p,q $ are distinct primes, we can conclude that $1+kq=1$ is the only value that expression $1+kq$ can take (i.e., $k=0$ situation).

Similarly, if $p^3-1$ is not divisible by $q$ but $1+kq$ divides $p^3$, where $p$, $q$ are distinct primes, then also can we conclude that the only value $1+kq$ can take is $1$?

2

There are 2 best solutions below

1
On

NO:

If $p=5, q=3, k=8$, then $3$ does not divide $p^3-1=124$, but $1+kq=25$ that divides $125$.

1
On

Given, $$p^3\not\equiv1\pmod{q}\\ \implies (p^3-1)\not\equiv 0\pmod{q} \implies (p-1)(p^2+p+1)\not\equiv 0\pmod{q}$$

Means, $q\nmid (p-1)(p^2+p+1)$. Means, $q$ is not dividing any of them. Hence we have, $$(p-1)\not\equiv0\pmod{q} ~~\wedge ~~ (p^2+p+1)\not\equiv 0\pmod{q} $$

But, we can't make same conclusion as we have made in case of $p^2-1$. In that case we have needed $p+1\equiv 1\pmod{q}$ to satisfy $p^2\equiv 1\pmod{q}$. Which implies, $p\equiv 0\pmod{q}$, but it is not possible, as $p$ is a prime no other number can divide it(as $q$ is distinct from $p$).But, here though we have $p-1\not\equiv 0\pmod{q}$. We can get factor of the form $1+kq$ for $p^3$. To get, a factor of the form $1+kq$ we need $$p^2+p+1\equiv 1\pmod{q}\\\implies p(p+1)\equiv 0\pmod{q}\\\implies p+1\equiv 0\pmod{q}... \\~~~~(\text{as, p and q are primes, they are coprime toeach other})$$

Hence, if $q|p+1$, we will have factor of the form $1+kq$.

As, the example shown in another answer with $p=5,q=3,k=8$, you can see that, as, $p+1=6$ is divisible by $3$, we have $1+kq=25$ a factor of $p^3$.