Let $n,p>1$ be positive integers and $p$ be prime. We know that $n|p-1$ and $p|n^3-1$. Prove that $4p-3$ is a perfect square.
Problem
Source:
Tags: number theory, Lte
21.09.2010 20:00
Here
21.09.2010 21:55
$n=1$ solution for any $p$. Therefore I think condition is: Let $n>1$ (not $p>1$) integer and $p$ prime. Because $1<n<p$ $p|n^3-1=(n-1)(n^2+n+1)\to p|n^2+n+1$ and $n|p-1\to p=kn+1,k\le n+1$. If $k<n+1$, then $p|n^2+n+1-p=n(n+1-k)$ contradition with $p>n$ and prime. Therefore $p=n^2+n+1$ and $4p-3=(2n+1)^2.$
30.12.2013 03:32
Once you arrive at $p=kn+1$ you can also observe that: \begin{eqnarray*} p\mid n^2+n+1\mid kn^2+kn+k \\ kn+1\mid \left(kn^2+kn+k\right)-n\left(kn+1\right) \\ kn+1\mid kn+k-n \\ k-n\ge 1\implies k=n+1\end{eqnarray*} The finish is the same as in Rust's.
20.02.2020 19:40
From the first divisibility, we know $p-1\geq n\rightarrow p\geq n+1$. Since $p|n^3-1\rightarrow p|(n-1)(n^2+n+1)$, and $p\geq n+1>n-1$, since $p$ is prime we have $\gcd (p,n-1)=1$, so $p|n^2+n+1$. Let $k$ be a positive integer such that $pk=n^2+n+1$. Taking this modulo $n$, we have $pk\equiv k\equiv1$ mod $n$. Now let $k=an+1$ for non-negative $a$. Then $p(an+1)=n^2+n+1\rightarrow apn+p=n^2+n+1$. Since $p\geq n+1$ and for $a\geq 1$, we have $apn>n^2$, we must have $a=0$, or $k=1$. Then $p=n^2+n+1$, which also satisfies the first divisibility. Finally, we have $4p-3=4n^2+4n+1=(2n+1)^2$, completing the proof.
03.11.2021 02:14
Here is my solution: Since: $n|p-1 \implies p=nk+1$ for some $k$ positive integer Of the condition: $p|(n^3-1) \implies p|(n-1)(n^2+n+1) \implies p|n-1$ or $p|n^2+n+1$ if $p|n-1$ $\implies p \le n-1$ but of the condition $n|p-1 \implies n \le p-1$ i.e $p \le n-1$ and $n \le p-1$. Then $p+1 \le n \le p-1$ so it's a contradiction Thus: $p|n^2+n+1 \implies p \le n^2+n+1$ Replacing: $nk+1|n^2+n+1$ $\implies nk+1|(n^2+n+1)k=n^2k+nk+k$ $\implies nk+1|n^2k+nk+k-n(nk+1)=nk+k-n$ $\implies nk+1 \le nk+k-n \implies n+1 \le k$ $\implies n(n+1)+1\le nk+1=p$ $n^2+n+1\le p$ but $p \le n^2+n+1$ $\implies p=n^2+n+1$ Thus: $4p-3=4n^2+4n+1=(2n+1)^2$.$\blacksquare$
28.11.2021 01:44
We can manipulate the conditions as follows: $n|p-1 \implies p=nk+1$ and $p\geq n+1$. $p|n^3-1 \leftrightarrow p|(n-1)(n^2+n+1) \implies$ either $p|n-1$ or $p|n^2+n+1$. But $p|n-1$ is not possible because $p\geq n+1$, so $p|n^2+n+1$. Hence, $p \leq n^2+n+1$. Additionally, $nk+1|kn^2+kn+k$, so $nk+1|nk+k-n$. Thus, $k \geq n+1$. Substituting $p=nk+1$ back in, we find $p\geq n^2+n+1$. However, we also know that $p \leq n^2+n+1$. Therefore, $p=n^2+n+1$, so $4p-3=4n^2+4n+1=(2n+1)^2$, which completes the problem.
09.03.2022 04:39
Let $p=nk+1$. We have $p\mid n^3-1=(n-1)(n^2+n+1)$. Now $p>n$, so $p\nmid n-1$, which implies $p\mid n^2+n+1$. So $nk+1\mid n^2+n+1$, which implies $nk+1\mid kn^2+kn+k-n(nk+1)=kn+k-n$. Thus, $nk+1\le nk+k-n\implies n+1\le k$. Thus, $n^2+n+1=n(n+1)+1\le nk+1=p$. So $p=n^2+n+1$. This implies $4p-3=4n^2+4n+1=(2n+1)^2$, as desired.
05.04.2022 23:11
Notice that $$n~|~p-1\implies n\le p-1\implies n+1\le p\implies p=nk+1$$for some $k$ and that $$p~|~(n-1)(n^2+n+1)\implies p\le n^2+n+1$$since $p~|~n-1$ is impossible in this case. Playing around with divisibility some more gives $$p~|~n^2+n+1~|~kn^2+kn+k\implies nk+1~|~kn^2+kn+k\implies nk+1~|~kn^2+kn+k-n(nk+1)$$which gives $$nk+1~|~kn+k-n\implies nk+1\le kn+k-n\implies n+1\le k.$$Using what we gathered previously, mainly that $p=nk+1$, we see that $$n(n+1)+1\le nk+1\implies n^2+n+1\le p$$which means we have $$n^2+n+1\le p\le n^2+n+1\implies p=n^2+n+1.$$So using this we see that $$4p-3=4(n^2+n+1)-3=(2n+1)^2$$which proves the desired $\square$
02.05.2022 02:43
Let $p=\ell n+1$ and notice $p\mid (n-1)(n^2+n+1)$ so $p\mid n-1$ or $p\mid n^2+n+1.$ We see the former implies $n+p\le n+p-2,$ a contradiction; hence, $p\mid n^2+n+1.$ Then, $$\ell n+1\mid \ell(n^2+n+1)-n(\ell n+1)=(\ell-1)n+\ell>0.$$Thus, \begin{align*}\ell n+1\le (\ell-1)n+\ell&\implies n+1\le \ell\\&\implies p\ge (n+1)n+1=n^2+n+1\\&\implies p=n^2+n+1\\&\implies 4p-3=4n^2+4n+1=(2n+1)^2.\end{align*}$\square$
08.05.2022 03:46
Write $p=kn+1$, and note that $p \mid (n-1)(n^2+n+1)$. Since $p > n-1$, it follows that $p \mid n^2+n+1$. Thus, for some integer $t$ we have that $t(kn+1) = n^2+n+1$, and noting that as both $kn+1$ and $n^2+n+1$ are congruent to $1 \pmod n$, $t$ must be congruent to $1 \pmod n$ as well. However, if $t \geq n+1$ then the left hand side of $t(kn+1) \geq (n+1)^2 > n^2+n+1$ which contradicts the divisibility condition, so $t=1$ and $p = n^2+n+1$. Finally, $4p-3 = 4(n^2+n+1)-3 = 4n^2+4n+1 = (2n+1)^2$, as desired.
20.12.2023 06:13
You have to love the hilarious answer extraction For size reasons we must have $p \mid n^2+n+1$. But then $np \mid n^2+n-p+1$; on the other hand $$np \geq n(n+1) > n^2+n-p+1$$so it follows $p = n^2+n+1$ and $4p-3 = (2n+1)^2$ is a perfect square.
04.01.2024 01:19
Is this problem have solution with LTE??
03.04.2024 12:25
Cute! , writing for storage purpose. $p|n^3-1 \implies p|(n-1)(n^2+n+1)$ , now if $p|n-1\implies p|n-1 , n|p-1 \implies p\geqslant n-1 \hspace{0.2cm} \text{and} \hspace{0.2cm} p \leqslant n-1$ that's a contradiction for a prime $p$. Hence $p|n^2+n+1 \implies p \leqslant n^2+n+1 \hspace{0.3cm} (\star)$ Now , since $n|p-1 \implies p=nt+1$ , for some $t \in \mathbb{Z}^{+}$ so we must have $$nt+1|n^2+n+1 \implies nt+1| n^2+n+1-(nt+1)^2 \implies nt+1| n(n-nt^2+1-2t)$$, since $\gcd(nt+1,n)=1$ we must have $nt+1|n-nt^2+1-2t \implies nt+1|n+1-t$ , now we also notice that if $n+1-t>0$ , then $$nt+1<n+1-t \implies n(t-1) \leqslant -t$$which is not posisble , hence $n+1 \leqslant t$ , which gives $n^2+n+1 \leqslant p \leqslant n^2+n+1 \implies p=n^2+n+1 \implies 4p-3=(2n+1)^2$. $\square$
23.06.2024 08:03
Note that $n|p-1 \implies p=nk+1$ and $p|n^3+1 \implies p|(n+1)(n^2+n+1) \implies p|n^2+n+1$. Note now that $p|k(n^2+n+1)-k(nk+1)=nk(n+1-k)$. Since $\gcd(nk+1,nk)=1$, we have that $nk+1|n+1-k$, but $n+1-k \leq nk+1$ so it must be negative or 0, thus $n+1-k \leq 0 \implies k \geq n+1$. However, if $k=n+1$ then $p=n(n+1)+1=n^2+n+1$, so that is actually the only value $k$ can take. That means $p=n^2+n+1, 4p-3=4n^2+4n+1=(2n+1)^2$ and we see that it is a perfect square.
26.06.2024 21:37
Since $p\mid (n-1)(n^2+n+1)$, we must have $p\mid n^2+n+1$ because $p>n-1$. Let $p=:an+1$ and $n^2+n+1=:pd$ for positive integers $a$ and $d$. Then $n^2+n+1=d(an+1)$. Taking mod $n$ gives $d\equiv 1\pmod{n}$ so $d=:bn+1$ for $b\in\mathbb{N}$. It follows that $abn+a+b=n+1$ so $n=\frac{1-a-b}{ab-1}$. If $ab-1$ is positive then $1-a-b$ is negative, which makes $n$ negative. Thus $ab-1$ is negative so $b=0$. Hence $d=1$ so $4d-3=(2n+1)^2$, as desired. $\square$
13.07.2024 17:32
From $n|p-1$, we get $n+1\leq p $. Then from the fact that $p|(n-1)(n^{2}+n+1)$, we get $p|n^{2}+n+1 \Rightarrow p \leq n^{2}+n+1$. Let $k$ be an positive integer such that $nk+1=p$. So, $nk+1 \leq n^{2}+n+1 \Rightarrow k \leq n+1$. Then $p=nk+1 \geq n^{2}+n+1 $. Which means, $p=n^{2}+n+1$, then it is easy to see that $4p-3$ is a perfect square.
18.08.2024 11:15
Iran 2005 Obviously we have that $p|n^2+n+1$, so we have that. $np \mid n^2+n-p+1$, but also. $$np \geq n(n+1) > n^2+n-p+1$$ Hence $p=n^2+n+1$, hence we are done.
18.08.2024 12:02
16.11.2024 18:12
$n|p-1$. So, $p=nk+1$ Also,$p-1 \geq n $ and $p \geq n+1$ $p|(n-1)(n^{2}+n+1)$. If $p|n-1$ then $n-1 \geq p$. However, $n-1 \geq p \geq n+1$ not possible, So $p|n^{2}+n+1$ and $p \leq n^{2}+n+1 \hspace{0.3cm} (\star)$. $p|n^{2}+n+1$, $nk+1|n^{2}+n+1$, $nk+1|k(n^{2}+n+1)-n(kn+1)$ $\Rightarrow$ $nk+1|nk+k-n$ So,$ nk+k-n \geq kn+1$, $n+1 \leq k$. we have $p =nk+1 \geq n(n+1)+1$ then $p \geq n^{2}+n+1 \hspace{0.3cm} (\star)$ From the $\hspace{0.cm} (\star)$ We got, $p=n^{2}+n+1$. , $4p-3=(2n+1)^{2}$
16.11.2024 22:58
Cool! Let $n^2 +n+1=kp$, where $k \in \mathbb{N}$ $\implies n(n+1)=kp-1$ $\implies n \mid kp-1$ Combining with $n \mid p-1$, we get $ n \leq gcd(kp-1,p-1)$ Note that if $2 \leq k$, then $gcd(kp-1,p-1)=1$, which would imply $n=1$ amd $p=3$. Hence, for rest of the primes, $k=1$ $\implies n^2 +n+1=p$ $\implies n^2+n+(1-p)=0$ Since this quadratic in $n$ has integer roots, the discriminant, that is $1-4(1-p)=4p-3$ mus be a perfect square. $\blacksquare$ [comment] This took way longer than it should have duh [/comment]