Let $x in mathbb{N}$ and let $p$ be a prime divisor of $x^4+x^3+x^2+x+1$, prove that $p = 5$ or $p equiv 1...
$begingroup$
This question already has an answer here:
Show that any prime divisor of $x^4+x^3+x^2+x+1$, with $xinmathbb{N}$, is $5$ or $1$ mod $5$
1 answer
Let $x in mathbb{N}$ and let $p$ be a prime divisor of $x^4+x^3+x^2+x+1$, prove that $p = 5$ or $p equiv 1 mod{5}$
Note that $(x^4+x^3+x^2+x+1)(x-1) = x^5 - 1$.
I tried reducing the equation $mod{5}$, which gave me some information on $x$, but I was not able to utilize this information.
elementary-number-theory prime-numbers divisibility
edited Dec 16 '18 at 17:18
Bill Dubuque
211k29192645
asked Dec 16 '18 at 13:57
Jens WagemakerJens Wagemaker
550312
$endgroup$
marked as duplicate by egreg, Community♦ Dec 16 '18 at 14:46
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Show that any prime divisor of $x^4+x^3+x^2+x+1$, with $xinmathbb{N}$, is $5$ or $1$ mod $5$
1 answer
Let $x in mathbb{N}$ and let $p$ be a prime divisor of $x^4+x^3+x^2+x+1$, prove that $p = 5$ or $p equiv 1 mod{5}$
Note that $(x^4+x^3+x^2+x+1)(x-1) = x^5 - 1$.
I tried reducing the equation $mod{5}$, which gave me some information on $x$, but I was not able to utilize this information.
elementary-number-theory prime-numbers divisibility
edited Dec 16 '18 at 17:18
Bill Dubuque
211k29192645
asked Dec 16 '18 at 13:57
Jens WagemakerJens Wagemaker
550312
$endgroup$
marked as duplicate by egreg, Community♦ Dec 16 '18 at 14:46
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
2
$begingroup$
Hint. Work $pmod p$. Note that the given equation tells us that $x^5-1equiv 0pmod p$.
$endgroup$
– lulu
Dec 16 '18 at 14:06
add a comment |
$begingroup$
This question already has an answer here:
Show that any prime divisor of $x^4+x^3+x^2+x+1$, with $xinmathbb{N}$, is $5$ or $1$ mod $5$
1 answer
Let $x in mathbb{N}$ and let $p$ be a prime divisor of $x^4+x^3+x^2+x+1$, prove that $p = 5$ or $p equiv 1 mod{5}$
Note that $(x^4+x^3+x^2+x+1)(x-1) = x^5 - 1$.
I tried reducing the equation $mod{5}$, which gave me some information on $x$, but I was not able to utilize this information.
elementary-number-theory prime-numbers divisibility
edited Dec 16 '18 at 17:18
Bill Dubuque
211k29192645
asked Dec 16 '18 at 13:57
Jens WagemakerJens Wagemaker
550312
$endgroup$
This question already has an answer here:
Show that any prime divisor of $x^4+x^3+x^2+x+1$, with $xinmathbb{N}$, is $5$ or $1$ mod $5$
1 answer
Let $x in mathbb{N}$ and let $p$ be a prime divisor of $x^4+x^3+x^2+x+1$, prove that $p = 5$ or $p equiv 1 mod{5}$
Note that $(x^4+x^3+x^2+x+1)(x-1) = x^5 - 1$.
I tried reducing the equation $mod{5}$, which gave me some information on $x$, but I was not able to utilize this information.
This question already has an answer here:
Show that any prime divisor of $x^4+x^3+x^2+x+1$, with $xinmathbb{N}$, is $5$ or $1$ mod $5$
1 answer
elementary-number-theory prime-numbers divisibility
elementary-number-theory prime-numbers divisibility
edited Dec 16 '18 at 17:18
Bill Dubuque
211k29192645
asked Dec 16 '18 at 13:57
Jens WagemakerJens Wagemaker
550312
edited Dec 16 '18 at 17:18
Bill Dubuque
211k29192645
asked Dec 16 '18 at 13:57
Jens WagemakerJens Wagemaker
550312
edited Dec 16 '18 at 17:18
Bill Dubuque
211k29192645
edited Dec 16 '18 at 17:18
Bill Dubuque
211k29192645
edited Dec 16 '18 at 17:18
Bill Dubuque
211k29192645
211k29192645
asked Dec 16 '18 at 13:57
Jens WagemakerJens Wagemaker
550312
asked Dec 16 '18 at 13:57
Jens WagemakerJens Wagemaker
550312
asked Dec 16 '18 at 13:57
Jens WagemakerJens Wagemaker
550312
550312
marked as duplicate by egreg, Community♦ Dec 16 '18 at 14:46
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by egreg, Community♦ Dec 16 '18 at 14:46
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
2
$begingroup$
Hint. Work $pmod p$. Note that the given equation tells us that $x^5-1equiv 0pmod p$.
$endgroup$
– lulu
Dec 16 '18 at 14:06
add a comment |
2
$begingroup$
Hint. Work $pmod p$. Note that the given equation tells us that $x^5-1equiv 0pmod p$.
$endgroup$
– lulu
Dec 16 '18 at 14:06
2
2
$begingroup$
Hint. Work $pmod p$. Note that the given equation tells us that $x^5-1equiv 0pmod p$.
$endgroup$
– lulu
Dec 16 '18 at 14:06
$begingroup$
Hint. Work $pmod p$. Note that the given equation tells us that $x^5-1equiv 0pmod p$.
$endgroup$
– lulu
Dec 16 '18 at 14:06
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
If $r= ord _p(x)$ then by Fermat $rmid p-1$ and by proposition $rmid 5$.
If $r=5$ then $p-1 =5k$ so $pequiv_5 1$
If $r=1$ then $x=1$ so $pmid 5$ and thus $p=5$.
answered Dec 16 '18 at 14:07
greedoidgreedoid
42.7k1153105
$endgroup$
1
$begingroup$
Is $r= ord _5(x)$ supposed to be $r= ord _p(x)$?
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:22
add a comment |
$begingroup$
Notice that $x^4+x^3+x^2+x+1 = frac{x^5-1}{x-1}$. Now, $frac{x^5-1}{x-1} equiv 0 pmod p implies x^5equiv 1 pmod p$. It follows that the order of $x$, call it $r$, $pmod p$ divides $5$. But $5$ is a prime number, hence $r=1,5$.
We know that The order of any number $pmod p$ divides $phi(p)$. If the order is $5$, then $5|(phi(p)=p-1) implies pequiv 1 pmod 5$. If otherwise, i.e. the order is $1$, then $x equiv 1 pmod p$. Therefore, $(x^1)^5-1 equiv 0 pmod 5$ implying that $5$ divides $x^5-1$.
answered Dec 16 '18 at 14:24
Maged SaeedMaged Saeed
8671417
$endgroup$
1
$begingroup$
In your first point: you are missing the case that the order equals 1. In your second point you miss the case 0, which is not a unit, hence not even has an order.
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:29
$begingroup$
@JensWagemaker, I updated the answer accordingly. Thanks for your notes.
$endgroup$
– Maged Saeed
Dec 16 '18 at 14:41
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If $r= ord _p(x)$ then by Fermat $rmid p-1$ and by proposition $rmid 5$.
If $r=5$ then $p-1 =5k$ so $pequiv_5 1$
If $r=1$ then $x=1$ so $pmid 5$ and thus $p=5$.
answered Dec 16 '18 at 14:07
greedoidgreedoid
42.7k1153105
$endgroup$
1
$begingroup$
Is $r= ord _5(x)$ supposed to be $r= ord _p(x)$?
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:22
add a comment |
$begingroup$
If $r= ord _p(x)$ then by Fermat $rmid p-1$ and by proposition $rmid 5$.
If $r=5$ then $p-1 =5k$ so $pequiv_5 1$
If $r=1$ then $x=1$ so $pmid 5$ and thus $p=5$.
answered Dec 16 '18 at 14:07
greedoidgreedoid
42.7k1153105
$endgroup$
1
$begingroup$
Is $r= ord _5(x)$ supposed to be $r= ord _p(x)$?
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:22
add a comment |
$begingroup$
If $r= ord _p(x)$ then by Fermat $rmid p-1$ and by proposition $rmid 5$.
If $r=5$ then $p-1 =5k$ so $pequiv_5 1$
If $r=1$ then $x=1$ so $pmid 5$ and thus $p=5$.
answered Dec 16 '18 at 14:07
greedoidgreedoid
42.7k1153105
$endgroup$
If $r= ord _p(x)$ then by Fermat $rmid p-1$ and by proposition $rmid 5$.
If $r=5$ then $p-1 =5k$ so $pequiv_5 1$
If $r=1$ then $x=1$ so $pmid 5$ and thus $p=5$.
answered Dec 16 '18 at 14:07
greedoidgreedoid
42.7k1153105
edited Dec 16 '18 at 14:40
answered Dec 16 '18 at 14:07
greedoidgreedoid
42.7k1153105
answered Dec 16 '18 at 14:07
greedoidgreedoid
42.7k1153105
answered Dec 16 '18 at 14:07
greedoidgreedoid
42.7k1153105
42.7k1153105
1
$begingroup$
Is $r= ord _5(x)$ supposed to be $r= ord _p(x)$?
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:22
add a comment |
1
$begingroup$
Is $r= ord _5(x)$ supposed to be $r= ord _p(x)$?
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:22
1
1
$begingroup$
Is $r= ord _5(x)$ supposed to be $r= ord _p(x)$?
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:22
$begingroup$
Is $r= ord _5(x)$ supposed to be $r= ord _p(x)$?
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:22
add a comment |
$begingroup$
Notice that $x^4+x^3+x^2+x+1 = frac{x^5-1}{x-1}$. Now, $frac{x^5-1}{x-1} equiv 0 pmod p implies x^5equiv 1 pmod p$. It follows that the order of $x$, call it $r$, $pmod p$ divides $5$. But $5$ is a prime number, hence $r=1,5$.
We know that The order of any number $pmod p$ divides $phi(p)$. If the order is $5$, then $5|(phi(p)=p-1) implies pequiv 1 pmod 5$. If otherwise, i.e. the order is $1$, then $x equiv 1 pmod p$. Therefore, $(x^1)^5-1 equiv 0 pmod 5$ implying that $5$ divides $x^5-1$.
answered Dec 16 '18 at 14:24
Maged SaeedMaged Saeed
8671417
$endgroup$
1
$begingroup$
In your first point: you are missing the case that the order equals 1. In your second point you miss the case 0, which is not a unit, hence not even has an order.
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:29
$begingroup$
@JensWagemaker, I updated the answer accordingly. Thanks for your notes.
$endgroup$
– Maged Saeed
Dec 16 '18 at 14:41
add a comment |
$begingroup$
Notice that $x^4+x^3+x^2+x+1 = frac{x^5-1}{x-1}$. Now, $frac{x^5-1}{x-1} equiv 0 pmod p implies x^5equiv 1 pmod p$. It follows that the order of $x$, call it $r$, $pmod p$ divides $5$. But $5$ is a prime number, hence $r=1,5$.
We know that The order of any number $pmod p$ divides $phi(p)$. If the order is $5$, then $5|(phi(p)=p-1) implies pequiv 1 pmod 5$. If otherwise, i.e. the order is $1$, then $x equiv 1 pmod p$. Therefore, $(x^1)^5-1 equiv 0 pmod 5$ implying that $5$ divides $x^5-1$.
answered Dec 16 '18 at 14:24
Maged SaeedMaged Saeed
8671417
$endgroup$
1
$begingroup$
In your first point: you are missing the case that the order equals 1. In your second point you miss the case 0, which is not a unit, hence not even has an order.
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:29
$begingroup$
@JensWagemaker, I updated the answer accordingly. Thanks for your notes.
$endgroup$
– Maged Saeed
Dec 16 '18 at 14:41
add a comment |
$begingroup$
Notice that $x^4+x^3+x^2+x+1 = frac{x^5-1}{x-1}$. Now, $frac{x^5-1}{x-1} equiv 0 pmod p implies x^5equiv 1 pmod p$. It follows that the order of $x$, call it $r$, $pmod p$ divides $5$. But $5$ is a prime number, hence $r=1,5$.
We know that The order of any number $pmod p$ divides $phi(p)$. If the order is $5$, then $5|(phi(p)=p-1) implies pequiv 1 pmod 5$. If otherwise, i.e. the order is $1$, then $x equiv 1 pmod p$. Therefore, $(x^1)^5-1 equiv 0 pmod 5$ implying that $5$ divides $x^5-1$.
answered Dec 16 '18 at 14:24
Maged SaeedMaged Saeed
8671417
$endgroup$
Notice that $x^4+x^3+x^2+x+1 = frac{x^5-1}{x-1}$. Now, $frac{x^5-1}{x-1} equiv 0 pmod p implies x^5equiv 1 pmod p$. It follows that the order of $x$, call it $r$, $pmod p$ divides $5$. But $5$ is a prime number, hence $r=1,5$.
We know that The order of any number $pmod p$ divides $phi(p)$. If the order is $5$, then $5|(phi(p)=p-1) implies pequiv 1 pmod 5$. If otherwise, i.e. the order is $1$, then $x equiv 1 pmod p$. Therefore, $(x^1)^5-1 equiv 0 pmod 5$ implying that $5$ divides $x^5-1$.
answered Dec 16 '18 at 14:24
Maged SaeedMaged Saeed
8671417
edited Dec 16 '18 at 14:47
answered Dec 16 '18 at 14:24
Maged SaeedMaged Saeed
8671417
answered Dec 16 '18 at 14:24
Maged SaeedMaged Saeed
8671417
answered Dec 16 '18 at 14:24
Maged SaeedMaged Saeed
8671417
8671417
1
$begingroup$
In your first point: you are missing the case that the order equals 1. In your second point you miss the case 0, which is not a unit, hence not even has an order.
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:29
$begingroup$
@JensWagemaker, I updated the answer accordingly. Thanks for your notes.
$endgroup$
– Maged Saeed
Dec 16 '18 at 14:41
add a comment |
1
$begingroup$
In your first point: you are missing the case that the order equals 1. In your second point you miss the case 0, which is not a unit, hence not even has an order.
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:29
$begingroup$
@JensWagemaker, I updated the answer accordingly. Thanks for your notes.
$endgroup$
– Maged Saeed
Dec 16 '18 at 14:41
1
1
$begingroup$
In your first point: you are missing the case that the order equals 1. In your second point you miss the case 0, which is not a unit, hence not even has an order.
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:29
$begingroup$
In your first point: you are missing the case that the order equals 1. In your second point you miss the case 0, which is not a unit, hence not even has an order.
$endgroup$
– Jens Wagemaker
Dec 16 '18 at 14:29
$begingroup$
@JensWagemaker, I updated the answer accordingly. Thanks for your notes.
$endgroup$
– Maged Saeed
Dec 16 '18 at 14:41
$begingroup$
@JensWagemaker, I updated the answer accordingly. Thanks for your notes.
$endgroup$
– Maged Saeed
Dec 16 '18 at 14:41
add a comment |
2
$begingroup$
Hint. Work $pmod p$. Note that the given equation tells us that $x^5-1equiv 0pmod p$.
$endgroup$
– lulu
Dec 16 '18 at 14:06