Mixing
Let $pgt 3$ be an prime. If $sum_{k=1}^{p-1} frac{1}{k}=frac{a}{b}$, where $gcd(a,b)=1$. Prove that $pmid a$....
$begingroup$
This question already has an answer here:
Proof that $sumlimits_i frac{(p-1)!}i$ is divisible by $p$
2 answers
Let $pgt 3$ be an prime. Suppose $$sum_{k=1}^{p-1} frac{1}{k}=frac{a}{b}$$ where $gcd(a,b)=1$. Prove that $a$ is divisible by $p$.
Please give me some hint. Sorry for this types of writing. I am not familiar with this.
elementary-number-theory prime-numbers divisibility
edited Jan 2 at 21:21
amWhy
192k28225439
asked Jan 2 at 8:31
Supriyo BanerjeeSupriyo Banerjee
1086
$endgroup$
marked as duplicate by rtybase, amWhy, Davide Giraudo, Cesareo, Leucippus Jan 3 at 0:42
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:
Proof that $sumlimits_i frac{(p-1)!}i$ is divisible by $p$
2 answers
Let $pgt 3$ be an prime. Suppose $$sum_{k=1}^{p-1} frac{1}{k}=frac{a}{b}$$ where $gcd(a,b)=1$. Prove that $a$ is divisible by $p$.
Please give me some hint. Sorry for this types of writing. I am not familiar with this.
elementary-number-theory prime-numbers divisibility
edited Jan 2 at 21:21
amWhy
192k28225439
asked Jan 2 at 8:31
Supriyo BanerjeeSupriyo Banerjee
1086
$endgroup$
marked as duplicate by rtybase, amWhy, Davide Giraudo, Cesareo, Leucippus Jan 3 at 0:42
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.
1
$begingroup$
Related: Wolstenholme's Theorem
$endgroup$
– TheSimpliFire
Jan 2 at 9:04
3
$begingroup$
HINT: working $pmod p$ you have $$sum_{k=1}^{p-1} k^{-1} = sum_{k=1}^{p-1} k equiv frac{p-1}{2} cdot p equiv 0$$ This makes sense because every integer $1 le k le p-1$ has a unique inverse $pmod p$ in that range.
$endgroup$
– Crostul
Jan 2 at 9:29
$begingroup$
Please check your hint .....
$endgroup$
– Supriyo Banerjee
Jan 2 at 9:33
$begingroup$
@Crostul you may have to be careful working mod $p$ though:..for example for some positive integer $n$ the equation $2^{-n} equiv_p 1$, but $2^{-n} not = 1$ for any positive integer $n$.
$endgroup$
– Mike
Jan 2 at 17:13
add a comment |
$begingroup$
This question already has an answer here:
Proof that $sumlimits_i frac{(p-1)!}i$ is divisible by $p$
2 answers
Let $pgt 3$ be an prime. Suppose $$sum_{k=1}^{p-1} frac{1}{k}=frac{a}{b}$$ where $gcd(a,b)=1$. Prove that $a$ is divisible by $p$.
Please give me some hint. Sorry for this types of writing. I am not familiar with this.
elementary-number-theory prime-numbers divisibility
edited Jan 2 at 21:21
amWhy
192k28225439
asked Jan 2 at 8:31
Supriyo BanerjeeSupriyo Banerjee
1086
$endgroup$
This question already has an answer here:
Proof that $sumlimits_i frac{(p-1)!}i$ is divisible by $p$
2 answers
Let $pgt 3$ be an prime. Suppose $$sum_{k=1}^{p-1} frac{1}{k}=frac{a}{b}$$ where $gcd(a,b)=1$. Prove that $a$ is divisible by $p$.
Please give me some hint. Sorry for this types of writing. I am not familiar with this.
This question already has an answer here:
Proof that $sumlimits_i frac{(p-1)!}i$ is divisible by $p$
2 answers
elementary-number-theory prime-numbers divisibility
elementary-number-theory prime-numbers divisibility
edited Jan 2 at 21:21
amWhy
192k28225439
asked Jan 2 at 8:31
Supriyo BanerjeeSupriyo Banerjee
1086
edited Jan 2 at 21:21
amWhy
192k28225439
asked Jan 2 at 8:31
Supriyo BanerjeeSupriyo Banerjee
1086
edited Jan 2 at 21:21
amWhy
192k28225439
edited Jan 2 at 21:21
amWhy
192k28225439
edited Jan 2 at 21:21
amWhy
192k28225439
192k28225439
asked Jan 2 at 8:31
Supriyo BanerjeeSupriyo Banerjee
1086
asked Jan 2 at 8:31
Supriyo BanerjeeSupriyo Banerjee
1086
asked Jan 2 at 8:31
Supriyo BanerjeeSupriyo Banerjee
1086
1086
marked as duplicate by rtybase, amWhy, Davide Giraudo, Cesareo, Leucippus Jan 3 at 0:42
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 rtybase, amWhy, Davide Giraudo, Cesareo, Leucippus Jan 3 at 0:42
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.
1
$begingroup$
Related: Wolstenholme's Theorem
$endgroup$
– TheSimpliFire
Jan 2 at 9:04
3
$begingroup$
HINT: working $pmod p$ you have $$sum_{k=1}^{p-1} k^{-1} = sum_{k=1}^{p-1} k equiv frac{p-1}{2} cdot p equiv 0$$ This makes sense because every integer $1 le k le p-1$ has a unique inverse $pmod p$ in that range.
$endgroup$
– Crostul
Jan 2 at 9:29
$begingroup$
Please check your hint .....
$endgroup$
– Supriyo Banerjee
Jan 2 at 9:33
$begingroup$
@Crostul you may have to be careful working mod $p$ though:..for example for some positive integer $n$ the equation $2^{-n} equiv_p 1$, but $2^{-n} not = 1$ for any positive integer $n$.
$endgroup$
– Mike
Jan 2 at 17:13
add a comment |
1
$begingroup$
Related: Wolstenholme's Theorem
$endgroup$
– TheSimpliFire
Jan 2 at 9:04
3
$begingroup$
HINT: working $pmod p$ you have $$sum_{k=1}^{p-1} k^{-1} = sum_{k=1}^{p-1} k equiv frac{p-1}{2} cdot p equiv 0$$ This makes sense because every integer $1 le k le p-1$ has a unique inverse $pmod p$ in that range.
$endgroup$
– Crostul
Jan 2 at 9:29
$begingroup$
Please check your hint .....
$endgroup$
– Supriyo Banerjee
Jan 2 at 9:33
$begingroup$
@Crostul you may have to be careful working mod $p$ though:..for example for some positive integer $n$ the equation $2^{-n} equiv_p 1$, but $2^{-n} not = 1$ for any positive integer $n$.
$endgroup$
– Mike
Jan 2 at 17:13
1
1
$begingroup$
Related: Wolstenholme's Theorem
$endgroup$
– TheSimpliFire
Jan 2 at 9:04
$begingroup$
Related: Wolstenholme's Theorem
$endgroup$
– TheSimpliFire
Jan 2 at 9:04
3
3
$begingroup$
HINT: working $pmod p$ you have $$sum_{k=1}^{p-1} k^{-1} = sum_{k=1}^{p-1} k equiv frac{p-1}{2} cdot p equiv 0$$ This makes sense because every integer $1 le k le p-1$ has a unique inverse $pmod p$ in that range.
$endgroup$
– Crostul
Jan 2 at 9:29
$begingroup$
HINT: working $pmod p$ you have $$sum_{k=1}^{p-1} k^{-1} = sum_{k=1}^{p-1} k equiv frac{p-1}{2} cdot p equiv 0$$ This makes sense because every integer $1 le k le p-1$ has a unique inverse $pmod p$ in that range.
$endgroup$
– Crostul
Jan 2 at 9:29
$begingroup$
Please check your hint .....
$endgroup$
– Supriyo Banerjee
Jan 2 at 9:33
$begingroup$
Please check your hint .....
$endgroup$
– Supriyo Banerjee
Jan 2 at 9:33
$begingroup$
@Crostul you may have to be careful working mod $p$ though:..for example for some positive integer $n$ the equation $2^{-n} equiv_p 1$, but $2^{-n} not = 1$ for any positive integer $n$.
$endgroup$
– Mike
Jan 2 at 17:13
$begingroup$
@Crostul you may have to be careful working mod $p$ though:..for example for some positive integer $n$ the equation $2^{-n} equiv_p 1$, but $2^{-n} not = 1$ for any positive integer $n$.
$endgroup$
– Mike
Jan 2 at 17:13
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Well
$$sum_{k=1}^{p-1} frac{1}{k} = sum_{k=1}^{p-1} frac{frac{(p-1)!}{k}}{(p-1)!}$$
Now $frac{(p-1)!}{k}$ is an integer for each such $k$, so writing $A=(p-1)!$, we note that $frac{A}{k} equiv_p (A mod p)(k^{-1} mod p)$. Thus
$$sum_{k=1}^{p-1} frac{(p-1)!}{k} doteq sum_{k=1}^{p-1} frac{A}{k} equiv_p sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p).$$
WE then use the fact that each element $k$ has a unqiue inverse to conclude
$$sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p) equiv_p sum_{k=1}^{p-1} (A mod p)k.$$
However, one can check that for a prime $p geq 3$ the following holds: $sum_{k=1}^{p-1} (k mod p) equiv_p 0$, concluding
$$sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p) equiv_p sum_{k=1}^{p-1} (A mod p)k equiv_p 0,$$
which gives you what you need to show [make sure you see why, it follows because $p$ does not divide $(p-1)!$].
answered Jan 2 at 17:29
MikeMike
3,373311
$endgroup$
add a comment |
$begingroup$
For $kleq {p-1over 2}$ let $q_k := {1over k(p-k)}$
So we have $$({1over 1}+{1over p-1})+({1over 2}+{1over p-2})+...+({1over {p-1over 2}}+{1over {p+1over 2}}) = {aover b}$$
$$pq_1+pq_2+...+pq_{p-1over 2} = {aover b}$$
Let $$q_1+q_2+...+q_{p-1over 2} = {cover (p-1)!}$$ for some integer $c$. So we have $$pcdot c cdot b = acdot (p-1)!implies pmid acdot (p-1)!implies pmid a$$
answered Jan 2 at 18:10
greedoidgreedoid
38.7k114797
$endgroup$
$begingroup$
Is this not enough answer to your question?
$endgroup$
– greedoid
Jan 8 at 18:46
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Well
$$sum_{k=1}^{p-1} frac{1}{k} = sum_{k=1}^{p-1} frac{frac{(p-1)!}{k}}{(p-1)!}$$
Now $frac{(p-1)!}{k}$ is an integer for each such $k$, so writing $A=(p-1)!$, we note that $frac{A}{k} equiv_p (A mod p)(k^{-1} mod p)$. Thus
$$sum_{k=1}^{p-1} frac{(p-1)!}{k} doteq sum_{k=1}^{p-1} frac{A}{k} equiv_p sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p).$$
WE then use the fact that each element $k$ has a unqiue inverse to conclude
$$sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p) equiv_p sum_{k=1}^{p-1} (A mod p)k.$$
However, one can check that for a prime $p geq 3$ the following holds: $sum_{k=1}^{p-1} (k mod p) equiv_p 0$, concluding
$$sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p) equiv_p sum_{k=1}^{p-1} (A mod p)k equiv_p 0,$$
which gives you what you need to show [make sure you see why, it follows because $p$ does not divide $(p-1)!$].
answered Jan 2 at 17:29
MikeMike
3,373311
$endgroup$
add a comment |
$begingroup$
Well
$$sum_{k=1}^{p-1} frac{1}{k} = sum_{k=1}^{p-1} frac{frac{(p-1)!}{k}}{(p-1)!}$$
Now $frac{(p-1)!}{k}$ is an integer for each such $k$, so writing $A=(p-1)!$, we note that $frac{A}{k} equiv_p (A mod p)(k^{-1} mod p)$. Thus
$$sum_{k=1}^{p-1} frac{(p-1)!}{k} doteq sum_{k=1}^{p-1} frac{A}{k} equiv_p sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p).$$
WE then use the fact that each element $k$ has a unqiue inverse to conclude
$$sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p) equiv_p sum_{k=1}^{p-1} (A mod p)k.$$
However, one can check that for a prime $p geq 3$ the following holds: $sum_{k=1}^{p-1} (k mod p) equiv_p 0$, concluding
$$sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p) equiv_p sum_{k=1}^{p-1} (A mod p)k equiv_p 0,$$
which gives you what you need to show [make sure you see why, it follows because $p$ does not divide $(p-1)!$].
answered Jan 2 at 17:29
MikeMike
3,373311
$endgroup$
add a comment |
$begingroup$
Well
$$sum_{k=1}^{p-1} frac{1}{k} = sum_{k=1}^{p-1} frac{frac{(p-1)!}{k}}{(p-1)!}$$
Now $frac{(p-1)!}{k}$ is an integer for each such $k$, so writing $A=(p-1)!$, we note that $frac{A}{k} equiv_p (A mod p)(k^{-1} mod p)$. Thus
$$sum_{k=1}^{p-1} frac{(p-1)!}{k} doteq sum_{k=1}^{p-1} frac{A}{k} equiv_p sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p).$$
WE then use the fact that each element $k$ has a unqiue inverse to conclude
$$sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p) equiv_p sum_{k=1}^{p-1} (A mod p)k.$$
However, one can check that for a prime $p geq 3$ the following holds: $sum_{k=1}^{p-1} (k mod p) equiv_p 0$, concluding
$$sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p) equiv_p sum_{k=1}^{p-1} (A mod p)k equiv_p 0,$$
which gives you what you need to show [make sure you see why, it follows because $p$ does not divide $(p-1)!$].
answered Jan 2 at 17:29
MikeMike
3,373311
$endgroup$
Well
$$sum_{k=1}^{p-1} frac{1}{k} = sum_{k=1}^{p-1} frac{frac{(p-1)!}{k}}{(p-1)!}$$
Now $frac{(p-1)!}{k}$ is an integer for each such $k$, so writing $A=(p-1)!$, we note that $frac{A}{k} equiv_p (A mod p)(k^{-1} mod p)$. Thus
$$sum_{k=1}^{p-1} frac{(p-1)!}{k} doteq sum_{k=1}^{p-1} frac{A}{k} equiv_p sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p).$$
WE then use the fact that each element $k$ has a unqiue inverse to conclude
$$sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p) equiv_p sum_{k=1}^{p-1} (A mod p)k.$$
However, one can check that for a prime $p geq 3$ the following holds: $sum_{k=1}^{p-1} (k mod p) equiv_p 0$, concluding
$$sum_{k=1}^{p-1} (A mod p)(k^{-1} mod p) equiv_p sum_{k=1}^{p-1} (A mod p)k equiv_p 0,$$
which gives you what you need to show [make sure you see why, it follows because $p$ does not divide $(p-1)!$].
answered Jan 2 at 17:29
MikeMike
3,373311
edited Jan 2 at 17:57
answered Jan 2 at 17:29
MikeMike
3,373311
answered Jan 2 at 17:29
MikeMike
3,373311
answered Jan 2 at 17:29
MikeMike
3,373311
3,373311
add a comment |
add a comment |
$begingroup$
For $kleq {p-1over 2}$ let $q_k := {1over k(p-k)}$
So we have $$({1over 1}+{1over p-1})+({1over 2}+{1over p-2})+...+({1over {p-1over 2}}+{1over {p+1over 2}}) = {aover b}$$
$$pq_1+pq_2+...+pq_{p-1over 2} = {aover b}$$
Let $$q_1+q_2+...+q_{p-1over 2} = {cover (p-1)!}$$ for some integer $c$. So we have $$pcdot c cdot b = acdot (p-1)!implies pmid acdot (p-1)!implies pmid a$$
answered Jan 2 at 18:10
greedoidgreedoid
38.7k114797
$endgroup$
$begingroup$
Is this not enough answer to your question?
$endgroup$
– greedoid
Jan 8 at 18:46
add a comment |
$begingroup$
For $kleq {p-1over 2}$ let $q_k := {1over k(p-k)}$
So we have $$({1over 1}+{1over p-1})+({1over 2}+{1over p-2})+...+({1over {p-1over 2}}+{1over {p+1over 2}}) = {aover b}$$
$$pq_1+pq_2+...+pq_{p-1over 2} = {aover b}$$
Let $$q_1+q_2+...+q_{p-1over 2} = {cover (p-1)!}$$ for some integer $c$. So we have $$pcdot c cdot b = acdot (p-1)!implies pmid acdot (p-1)!implies pmid a$$
answered Jan 2 at 18:10
greedoidgreedoid
38.7k114797
$endgroup$
$begingroup$
Is this not enough answer to your question?
$endgroup$
– greedoid
Jan 8 at 18:46
add a comment |
$begingroup$
For $kleq {p-1over 2}$ let $q_k := {1over k(p-k)}$
So we have $$({1over 1}+{1over p-1})+({1over 2}+{1over p-2})+...+({1over {p-1over 2}}+{1over {p+1over 2}}) = {aover b}$$
$$pq_1+pq_2+...+pq_{p-1over 2} = {aover b}$$
Let $$q_1+q_2+...+q_{p-1over 2} = {cover (p-1)!}$$ for some integer $c$. So we have $$pcdot c cdot b = acdot (p-1)!implies pmid acdot (p-1)!implies pmid a$$
answered Jan 2 at 18:10
greedoidgreedoid
38.7k114797
$endgroup$
For $kleq {p-1over 2}$ let $q_k := {1over k(p-k)}$
So we have $$({1over 1}+{1over p-1})+({1over 2}+{1over p-2})+...+({1over {p-1over 2}}+{1over {p+1over 2}}) = {aover b}$$
$$pq_1+pq_2+...+pq_{p-1over 2} = {aover b}$$
Let $$q_1+q_2+...+q_{p-1over 2} = {cover (p-1)!}$$ for some integer $c$. So we have $$pcdot c cdot b = acdot (p-1)!implies pmid acdot (p-1)!implies pmid a$$
answered Jan 2 at 18:10
greedoidgreedoid
38.7k114797
answered Jan 2 at 18:10
greedoidgreedoid
38.7k114797
answered Jan 2 at 18:10
greedoidgreedoid
38.7k114797
answered Jan 2 at 18:10
greedoidgreedoid
38.7k114797
38.7k114797
$begingroup$
Is this not enough answer to your question?
$endgroup$
– greedoid
Jan 8 at 18:46
add a comment |
$begingroup$
Is this not enough answer to your question?
$endgroup$
– greedoid
Jan 8 at 18:46
$begingroup$
Is this not enough answer to your question?
$endgroup$
– greedoid
Jan 8 at 18:46
$begingroup$
Is this not enough answer to your question?
$endgroup$
– greedoid
Jan 8 at 18:46
add a comment |
1
$begingroup$
Related: Wolstenholme's Theorem
$endgroup$
– TheSimpliFire
Jan 2 at 9:04
3
$begingroup$
HINT: working $pmod p$ you have $$sum_{k=1}^{p-1} k^{-1} = sum_{k=1}^{p-1} k equiv frac{p-1}{2} cdot p equiv 0$$ This makes sense because every integer $1 le k le p-1$ has a unique inverse $pmod p$ in that range.
$endgroup$
– Crostul
Jan 2 at 9:29
$begingroup$
Please check your hint .....
$endgroup$
– Supriyo Banerjee
Jan 2 at 9:33
$begingroup$
@Crostul you may have to be careful working mod $p$ though:..for example for some positive integer $n$ the equation $2^{-n} equiv_p 1$, but $2^{-n} not = 1$ for any positive integer $n$.
$endgroup$
– Mike
Jan 2 at 17:13