Find the values of p and q
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
If $p^3+p=q^2+q$ where $p$ and $q$ are prime numbers,
Find all the solutions (p, q)
I tried to solve this exercise using that:
$p^2 = -1(textmod , q)$ and $q = -1(textmod , p)$;
So: $q+1=ap$ and $p^2+1=bq$, where $b$ and $q$ integers.
Then I tried to solve a quadratic equation, but I could not finish the problem
number-theory elementary-number-theory prime-numbers
add a comment |Â
up vote
3
down vote
favorite
If $p^3+p=q^2+q$ where $p$ and $q$ are prime numbers,
Find all the solutions (p, q)
I tried to solve this exercise using that:
$p^2 = -1(textmod , q)$ and $q = -1(textmod , p)$;
So: $q+1=ap$ and $p^2+1=bq$, where $b$ and $q$ integers.
Then I tried to solve a quadratic equation, but I could not finish the problem
number-theory elementary-number-theory prime-numbers
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
If $p^3+p=q^2+q$ where $p$ and $q$ are prime numbers,
Find all the solutions (p, q)
I tried to solve this exercise using that:
$p^2 = -1(textmod , q)$ and $q = -1(textmod , p)$;
So: $q+1=ap$ and $p^2+1=bq$, where $b$ and $q$ integers.
Then I tried to solve a quadratic equation, but I could not finish the problem
number-theory elementary-number-theory prime-numbers
If $p^3+p=q^2+q$ where $p$ and $q$ are prime numbers,
Find all the solutions (p, q)
I tried to solve this exercise using that:
$p^2 = -1(textmod , q)$ and $q = -1(textmod , p)$;
So: $q+1=ap$ and $p^2+1=bq$, where $b$ and $q$ integers.
Then I tried to solve a quadratic equation, but I could not finish the problem
number-theory elementary-number-theory prime-numbers
number-theory elementary-number-theory prime-numbers
edited 19 mins ago
asked 30 mins ago
Matheus Domingos
856
856
add a comment |Â
add a comment |Â
4 Answers
4
active
oldest
votes
up vote
1
down vote
accepted
$$p^3+p=q^2+q implies p|q^2+q implies p|q mathrmor p|(q+1).$$
Obviously, $pneq q$, so $pnmid q$. Thus, we can set $q=kp-1$. This then reduces to
$$p^2-k^2p+(k+1)=0,$$
which has an integer solution iff $k^4-4k-4$ is a square. Can you see why this is not the case for large $k$, and determine the solutions from there?
Oh thanks, now I know how to finish it, thanks
â Matheus Domingos
17 mins ago
Is there a better way to do that? I learned in high school to solve that using k^4-4k-4=a^2 and then I have to study that. Is there a better way to do that?
â Matheus Domingos
24 secs ago
add a comment |Â
up vote
2
down vote
Hint: Since $p$ divides $p^3+p$, also $p$ divides $q(q+1)$, hence $p$ either divides $q$ or $p$ divides $q+1$, because $p$ is prime. Can you finish it?
add a comment |Â
up vote
2
down vote
Clearly $pneq q$, and because $p$ and $q$ are prime and
$$p(p^2+1)=p^3+p=q^2+q=q(q+1),$$
we must have $pmid q+1$ and $qmid p^2+1$. Write
$$q+1=apqquadtext and qquad p^2+1=bq,$$
to find that $p^2-abp+b+1=0$. In particular $b+1equiv0pmodp$, say $b=cp-1$, but then
$$p^2+1=(cp-1)q=(cp-1)(ap-1)=acp^2-(a+c)p+1.$$
Note that $a$, $b$ and $c$ are positive integers, and that $a>1$ as otherwise $p=q+1$, so $(p,q)=(3,2)$ which is not a solution. The equation above implies that
$$(ac-1)p=a+c,$$
and as $pgeq2$ clearly we cannot have $a,cgeq2$. Hence $c=1$ and so
$$p^2+1=bq=(cp-1)q=(p-1)q.$$
In particular $p-1mid p^2+1$. As $p-1mid p^2-1$ it follows that $p-1=2$, so $p=3$ and hence $q=5$.
How do I finish this solution? Finding all the solution?
â Matheus Domingos
8 mins ago
@MatheusDomingos I completed the solution for you.
â Servaes
7 mins ago
1
Thank you, now I understood the limitation. I need to have a+c=>ac-1... What implies that (a-1)(c-1)=>2. Thanks
â Matheus Domingos
1 min ago
I rearranged the argument a bit, as in fact $a>1$ follows very easily earlier on, simpifying the final step.
â Servaes
35 secs ago
add a comment |Â
up vote
2
down vote
Remember that if $a,b$ are positive integers such that $amid b$ then $aleq b$. I'll be using this frekvently here.
From $$p(p^2+1)= q(q+1)implies pmid q;;;rm or;;;pmid q+1$$
1. case $pmid q$, then $q+1mid p^2+1$. Write $q+1=s$ then we get $$psmid (p^2+1)(s-1) = p^2s-p^2+s-1implies psmid p^2-s+1$$
Since $p^2+1geq s$ we have 2 subcases:
1.1 case $p^2+1>s$, then $psleq p^2-s+1$ so $s(p+1)leq p^2+1$, and thus $$sleq p^2+1over p+1 <pimplies sleq p-1$$
So $q+1leq p-1 leq q-1$ and thus no solution.
1.2 case $p^2+1=s$, then $q^2+1 = q+1$ and again no solution.
2. case $pmid q+1$, then $qmid p^2+1$. Then we get $$pqmid (p^2+1)(q+1) = p^2q+p^2+q+1implies pqmid p^2+q+1$$
so we have $pqleq p^2+q+1$ so $q leq p^2+1over p-1 leq p+2$ if $pgeq 3$.
So if $pgeq 3$ and since $pmid q$ that $qin p,p+1,p+2$ which is easy to finish by hand.
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
$$p^3+p=q^2+q implies p|q^2+q implies p|q mathrmor p|(q+1).$$
Obviously, $pneq q$, so $pnmid q$. Thus, we can set $q=kp-1$. This then reduces to
$$p^2-k^2p+(k+1)=0,$$
which has an integer solution iff $k^4-4k-4$ is a square. Can you see why this is not the case for large $k$, and determine the solutions from there?
Oh thanks, now I know how to finish it, thanks
â Matheus Domingos
17 mins ago
Is there a better way to do that? I learned in high school to solve that using k^4-4k-4=a^2 and then I have to study that. Is there a better way to do that?
â Matheus Domingos
24 secs ago
add a comment |Â
up vote
1
down vote
accepted
$$p^3+p=q^2+q implies p|q^2+q implies p|q mathrmor p|(q+1).$$
Obviously, $pneq q$, so $pnmid q$. Thus, we can set $q=kp-1$. This then reduces to
$$p^2-k^2p+(k+1)=0,$$
which has an integer solution iff $k^4-4k-4$ is a square. Can you see why this is not the case for large $k$, and determine the solutions from there?
Oh thanks, now I know how to finish it, thanks
â Matheus Domingos
17 mins ago
Is there a better way to do that? I learned in high school to solve that using k^4-4k-4=a^2 and then I have to study that. Is there a better way to do that?
â Matheus Domingos
24 secs ago
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
$$p^3+p=q^2+q implies p|q^2+q implies p|q mathrmor p|(q+1).$$
Obviously, $pneq q$, so $pnmid q$. Thus, we can set $q=kp-1$. This then reduces to
$$p^2-k^2p+(k+1)=0,$$
which has an integer solution iff $k^4-4k-4$ is a square. Can you see why this is not the case for large $k$, and determine the solutions from there?
$$p^3+p=q^2+q implies p|q^2+q implies p|q mathrmor p|(q+1).$$
Obviously, $pneq q$, so $pnmid q$. Thus, we can set $q=kp-1$. This then reduces to
$$p^2-k^2p+(k+1)=0,$$
which has an integer solution iff $k^4-4k-4$ is a square. Can you see why this is not the case for large $k$, and determine the solutions from there?
edited 12 mins ago
answered 19 mins ago
Carl Schildkraut
8,98711238
8,98711238
Oh thanks, now I know how to finish it, thanks
â Matheus Domingos
17 mins ago
Is there a better way to do that? I learned in high school to solve that using k^4-4k-4=a^2 and then I have to study that. Is there a better way to do that?
â Matheus Domingos
24 secs ago
add a comment |Â
Oh thanks, now I know how to finish it, thanks
â Matheus Domingos
17 mins ago
Is there a better way to do that? I learned in high school to solve that using k^4-4k-4=a^2 and then I have to study that. Is there a better way to do that?
â Matheus Domingos
24 secs ago
Oh thanks, now I know how to finish it, thanks
â Matheus Domingos
17 mins ago
Oh thanks, now I know how to finish it, thanks
â Matheus Domingos
17 mins ago
Is there a better way to do that? I learned in high school to solve that using k^4-4k-4=a^2 and then I have to study that. Is there a better way to do that?
â Matheus Domingos
24 secs ago
Is there a better way to do that? I learned in high school to solve that using k^4-4k-4=a^2 and then I have to study that. Is there a better way to do that?
â Matheus Domingos
24 secs ago
add a comment |Â
up vote
2
down vote
Hint: Since $p$ divides $p^3+p$, also $p$ divides $q(q+1)$, hence $p$ either divides $q$ or $p$ divides $q+1$, because $p$ is prime. Can you finish it?
add a comment |Â
up vote
2
down vote
Hint: Since $p$ divides $p^3+p$, also $p$ divides $q(q+1)$, hence $p$ either divides $q$ or $p$ divides $q+1$, because $p$ is prime. Can you finish it?
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Hint: Since $p$ divides $p^3+p$, also $p$ divides $q(q+1)$, hence $p$ either divides $q$ or $p$ divides $q+1$, because $p$ is prime. Can you finish it?
Hint: Since $p$ divides $p^3+p$, also $p$ divides $q(q+1)$, hence $p$ either divides $q$ or $p$ divides $q+1$, because $p$ is prime. Can you finish it?
answered 20 mins ago
Dietrich Burde
75.7k64185
75.7k64185
add a comment |Â
add a comment |Â
up vote
2
down vote
Clearly $pneq q$, and because $p$ and $q$ are prime and
$$p(p^2+1)=p^3+p=q^2+q=q(q+1),$$
we must have $pmid q+1$ and $qmid p^2+1$. Write
$$q+1=apqquadtext and qquad p^2+1=bq,$$
to find that $p^2-abp+b+1=0$. In particular $b+1equiv0pmodp$, say $b=cp-1$, but then
$$p^2+1=(cp-1)q=(cp-1)(ap-1)=acp^2-(a+c)p+1.$$
Note that $a$, $b$ and $c$ are positive integers, and that $a>1$ as otherwise $p=q+1$, so $(p,q)=(3,2)$ which is not a solution. The equation above implies that
$$(ac-1)p=a+c,$$
and as $pgeq2$ clearly we cannot have $a,cgeq2$. Hence $c=1$ and so
$$p^2+1=bq=(cp-1)q=(p-1)q.$$
In particular $p-1mid p^2+1$. As $p-1mid p^2-1$ it follows that $p-1=2$, so $p=3$ and hence $q=5$.
How do I finish this solution? Finding all the solution?
â Matheus Domingos
8 mins ago
@MatheusDomingos I completed the solution for you.
â Servaes
7 mins ago
1
Thank you, now I understood the limitation. I need to have a+c=>ac-1... What implies that (a-1)(c-1)=>2. Thanks
â Matheus Domingos
1 min ago
I rearranged the argument a bit, as in fact $a>1$ follows very easily earlier on, simpifying the final step.
â Servaes
35 secs ago
add a comment |Â
up vote
2
down vote
Clearly $pneq q$, and because $p$ and $q$ are prime and
$$p(p^2+1)=p^3+p=q^2+q=q(q+1),$$
we must have $pmid q+1$ and $qmid p^2+1$. Write
$$q+1=apqquadtext and qquad p^2+1=bq,$$
to find that $p^2-abp+b+1=0$. In particular $b+1equiv0pmodp$, say $b=cp-1$, but then
$$p^2+1=(cp-1)q=(cp-1)(ap-1)=acp^2-(a+c)p+1.$$
Note that $a$, $b$ and $c$ are positive integers, and that $a>1$ as otherwise $p=q+1$, so $(p,q)=(3,2)$ which is not a solution. The equation above implies that
$$(ac-1)p=a+c,$$
and as $pgeq2$ clearly we cannot have $a,cgeq2$. Hence $c=1$ and so
$$p^2+1=bq=(cp-1)q=(p-1)q.$$
In particular $p-1mid p^2+1$. As $p-1mid p^2-1$ it follows that $p-1=2$, so $p=3$ and hence $q=5$.
How do I finish this solution? Finding all the solution?
â Matheus Domingos
8 mins ago
@MatheusDomingos I completed the solution for you.
â Servaes
7 mins ago
1
Thank you, now I understood the limitation. I need to have a+c=>ac-1... What implies that (a-1)(c-1)=>2. Thanks
â Matheus Domingos
1 min ago
I rearranged the argument a bit, as in fact $a>1$ follows very easily earlier on, simpifying the final step.
â Servaes
35 secs ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Clearly $pneq q$, and because $p$ and $q$ are prime and
$$p(p^2+1)=p^3+p=q^2+q=q(q+1),$$
we must have $pmid q+1$ and $qmid p^2+1$. Write
$$q+1=apqquadtext and qquad p^2+1=bq,$$
to find that $p^2-abp+b+1=0$. In particular $b+1equiv0pmodp$, say $b=cp-1$, but then
$$p^2+1=(cp-1)q=(cp-1)(ap-1)=acp^2-(a+c)p+1.$$
Note that $a$, $b$ and $c$ are positive integers, and that $a>1$ as otherwise $p=q+1$, so $(p,q)=(3,2)$ which is not a solution. The equation above implies that
$$(ac-1)p=a+c,$$
and as $pgeq2$ clearly we cannot have $a,cgeq2$. Hence $c=1$ and so
$$p^2+1=bq=(cp-1)q=(p-1)q.$$
In particular $p-1mid p^2+1$. As $p-1mid p^2-1$ it follows that $p-1=2$, so $p=3$ and hence $q=5$.
Clearly $pneq q$, and because $p$ and $q$ are prime and
$$p(p^2+1)=p^3+p=q^2+q=q(q+1),$$
we must have $pmid q+1$ and $qmid p^2+1$. Write
$$q+1=apqquadtext and qquad p^2+1=bq,$$
to find that $p^2-abp+b+1=0$. In particular $b+1equiv0pmodp$, say $b=cp-1$, but then
$$p^2+1=(cp-1)q=(cp-1)(ap-1)=acp^2-(a+c)p+1.$$
Note that $a$, $b$ and $c$ are positive integers, and that $a>1$ as otherwise $p=q+1$, so $(p,q)=(3,2)$ which is not a solution. The equation above implies that
$$(ac-1)p=a+c,$$
and as $pgeq2$ clearly we cannot have $a,cgeq2$. Hence $c=1$ and so
$$p^2+1=bq=(cp-1)q=(p-1)q.$$
In particular $p-1mid p^2+1$. As $p-1mid p^2-1$ it follows that $p-1=2$, so $p=3$ and hence $q=5$.
edited 7 mins ago
answered 20 mins ago
Servaes
18.8k33684
18.8k33684
How do I finish this solution? Finding all the solution?
â Matheus Domingos
8 mins ago
@MatheusDomingos I completed the solution for you.
â Servaes
7 mins ago
1
Thank you, now I understood the limitation. I need to have a+c=>ac-1... What implies that (a-1)(c-1)=>2. Thanks
â Matheus Domingos
1 min ago
I rearranged the argument a bit, as in fact $a>1$ follows very easily earlier on, simpifying the final step.
â Servaes
35 secs ago
add a comment |Â
How do I finish this solution? Finding all the solution?
â Matheus Domingos
8 mins ago
@MatheusDomingos I completed the solution for you.
â Servaes
7 mins ago
1
Thank you, now I understood the limitation. I need to have a+c=>ac-1... What implies that (a-1)(c-1)=>2. Thanks
â Matheus Domingos
1 min ago
I rearranged the argument a bit, as in fact $a>1$ follows very easily earlier on, simpifying the final step.
â Servaes
35 secs ago
How do I finish this solution? Finding all the solution?
â Matheus Domingos
8 mins ago
How do I finish this solution? Finding all the solution?
â Matheus Domingos
8 mins ago
@MatheusDomingos I completed the solution for you.
â Servaes
7 mins ago
@MatheusDomingos I completed the solution for you.
â Servaes
7 mins ago
1
1
Thank you, now I understood the limitation. I need to have a+c=>ac-1... What implies that (a-1)(c-1)=>2. Thanks
â Matheus Domingos
1 min ago
Thank you, now I understood the limitation. I need to have a+c=>ac-1... What implies that (a-1)(c-1)=>2. Thanks
â Matheus Domingos
1 min ago
I rearranged the argument a bit, as in fact $a>1$ follows very easily earlier on, simpifying the final step.
â Servaes
35 secs ago
I rearranged the argument a bit, as in fact $a>1$ follows very easily earlier on, simpifying the final step.
â Servaes
35 secs ago
add a comment |Â
up vote
2
down vote
Remember that if $a,b$ are positive integers such that $amid b$ then $aleq b$. I'll be using this frekvently here.
From $$p(p^2+1)= q(q+1)implies pmid q;;;rm or;;;pmid q+1$$
1. case $pmid q$, then $q+1mid p^2+1$. Write $q+1=s$ then we get $$psmid (p^2+1)(s-1) = p^2s-p^2+s-1implies psmid p^2-s+1$$
Since $p^2+1geq s$ we have 2 subcases:
1.1 case $p^2+1>s$, then $psleq p^2-s+1$ so $s(p+1)leq p^2+1$, and thus $$sleq p^2+1over p+1 <pimplies sleq p-1$$
So $q+1leq p-1 leq q-1$ and thus no solution.
1.2 case $p^2+1=s$, then $q^2+1 = q+1$ and again no solution.
2. case $pmid q+1$, then $qmid p^2+1$. Then we get $$pqmid (p^2+1)(q+1) = p^2q+p^2+q+1implies pqmid p^2+q+1$$
so we have $pqleq p^2+q+1$ so $q leq p^2+1over p-1 leq p+2$ if $pgeq 3$.
So if $pgeq 3$ and since $pmid q$ that $qin p,p+1,p+2$ which is easy to finish by hand.
add a comment |Â
up vote
2
down vote
Remember that if $a,b$ are positive integers such that $amid b$ then $aleq b$. I'll be using this frekvently here.
From $$p(p^2+1)= q(q+1)implies pmid q;;;rm or;;;pmid q+1$$
1. case $pmid q$, then $q+1mid p^2+1$. Write $q+1=s$ then we get $$psmid (p^2+1)(s-1) = p^2s-p^2+s-1implies psmid p^2-s+1$$
Since $p^2+1geq s$ we have 2 subcases:
1.1 case $p^2+1>s$, then $psleq p^2-s+1$ so $s(p+1)leq p^2+1$, and thus $$sleq p^2+1over p+1 <pimplies sleq p-1$$
So $q+1leq p-1 leq q-1$ and thus no solution.
1.2 case $p^2+1=s$, then $q^2+1 = q+1$ and again no solution.
2. case $pmid q+1$, then $qmid p^2+1$. Then we get $$pqmid (p^2+1)(q+1) = p^2q+p^2+q+1implies pqmid p^2+q+1$$
so we have $pqleq p^2+q+1$ so $q leq p^2+1over p-1 leq p+2$ if $pgeq 3$.
So if $pgeq 3$ and since $pmid q$ that $qin p,p+1,p+2$ which is easy to finish by hand.
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Remember that if $a,b$ are positive integers such that $amid b$ then $aleq b$. I'll be using this frekvently here.
From $$p(p^2+1)= q(q+1)implies pmid q;;;rm or;;;pmid q+1$$
1. case $pmid q$, then $q+1mid p^2+1$. Write $q+1=s$ then we get $$psmid (p^2+1)(s-1) = p^2s-p^2+s-1implies psmid p^2-s+1$$
Since $p^2+1geq s$ we have 2 subcases:
1.1 case $p^2+1>s$, then $psleq p^2-s+1$ so $s(p+1)leq p^2+1$, and thus $$sleq p^2+1over p+1 <pimplies sleq p-1$$
So $q+1leq p-1 leq q-1$ and thus no solution.
1.2 case $p^2+1=s$, then $q^2+1 = q+1$ and again no solution.
2. case $pmid q+1$, then $qmid p^2+1$. Then we get $$pqmid (p^2+1)(q+1) = p^2q+p^2+q+1implies pqmid p^2+q+1$$
so we have $pqleq p^2+q+1$ so $q leq p^2+1over p-1 leq p+2$ if $pgeq 3$.
So if $pgeq 3$ and since $pmid q$ that $qin p,p+1,p+2$ which is easy to finish by hand.
Remember that if $a,b$ are positive integers such that $amid b$ then $aleq b$. I'll be using this frekvently here.
From $$p(p^2+1)= q(q+1)implies pmid q;;;rm or;;;pmid q+1$$
1. case $pmid q$, then $q+1mid p^2+1$. Write $q+1=s$ then we get $$psmid (p^2+1)(s-1) = p^2s-p^2+s-1implies psmid p^2-s+1$$
Since $p^2+1geq s$ we have 2 subcases:
1.1 case $p^2+1>s$, then $psleq p^2-s+1$ so $s(p+1)leq p^2+1$, and thus $$sleq p^2+1over p+1 <pimplies sleq p-1$$
So $q+1leq p-1 leq q-1$ and thus no solution.
1.2 case $p^2+1=s$, then $q^2+1 = q+1$ and again no solution.
2. case $pmid q+1$, then $qmid p^2+1$. Then we get $$pqmid (p^2+1)(q+1) = p^2q+p^2+q+1implies pqmid p^2+q+1$$
so we have $pqleq p^2+q+1$ so $q leq p^2+1over p-1 leq p+2$ if $pgeq 3$.
So if $pgeq 3$ and since $pmid q$ that $qin p,p+1,p+2$ which is easy to finish by hand.
edited 2 mins ago
answered 18 mins ago
greedoid
30.7k94184
30.7k94184
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2944795%2ffind-the-values-of-p-and-q%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password