Mixing
How to evaluate $ prod_1le i <jlefracp-12j^2-i^2 pmod p$
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
While doing my research on elementary number theory, I came across the following problem which I cannot overcome: Let $p$ be an odd prime, $g$ be any primitive of $p$. Define
$$f(p)=prod_1le i <jlefracp-12j^2-i^2pmod p$$ and
$$h(p,g)=prod_1le i <jlefracp-12g^2j-g^2i pmod p .$$ What I want to know is the relationship between $f(p)$ and $h(p,g)$. I calculated the first one hundred primes and find that either $f(p)+h(p,g)=p $ or $f(p)=h(p,g) $. For example $f(17)=4 $ , $h(17,5)=13 $ and $f(73)=h(73,11)=46 $. I believe that this is true for all primes $p$ and all primitives $g$.
Now my questions are :
- Does it true that we always have $f(p)+h(p,g)=p $ or $f(p)=h(p,g) $
Is it possible to evaluate $f(p)$ and $h(p,g)$ and find the condition when does $f(p)+h(p,g)=p $ and $f(p)=h(p,g) $
I am eager to know any answer, link, or hints to this problem, thank you!!
number-theory elementary-number-theory prime-numbers primitive-roots
asked Jul 27 at 14:44
王æÂŽè¿œ
18813
add a comment |Â
up vote
2
down vote
favorite
While doing my research on elementary number theory, I came across the following problem which I cannot overcome: Let $p$ be an odd prime, $g$ be any primitive of $p$. Define
$$f(p)=prod_1le i <jlefracp-12j^2-i^2pmod p$$ and
$$h(p,g)=prod_1le i <jlefracp-12g^2j-g^2i pmod p .$$ What I want to know is the relationship between $f(p)$ and $h(p,g)$. I calculated the first one hundred primes and find that either $f(p)+h(p,g)=p $ or $f(p)=h(p,g) $. For example $f(17)=4 $ , $h(17,5)=13 $ and $f(73)=h(73,11)=46 $. I believe that this is true for all primes $p$ and all primitives $g$.
Now my questions are :
- Does it true that we always have $f(p)+h(p,g)=p $ or $f(p)=h(p,g) $
Is it possible to evaluate $f(p)$ and $h(p,g)$ and find the condition when does $f(p)+h(p,g)=p $ and $f(p)=h(p,g) $
I am eager to know any answer, link, or hints to this problem, thank you!!
number-theory elementary-number-theory prime-numbers primitive-roots
asked Jul 27 at 14:44
王æÂŽè¿œ
18813
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
While doing my research on elementary number theory, I came across the following problem which I cannot overcome: Let $p$ be an odd prime, $g$ be any primitive of $p$. Define
$$f(p)=prod_1le i <jlefracp-12j^2-i^2pmod p$$ and
$$h(p,g)=prod_1le i <jlefracp-12g^2j-g^2i pmod p .$$ What I want to know is the relationship between $f(p)$ and $h(p,g)$. I calculated the first one hundred primes and find that either $f(p)+h(p,g)=p $ or $f(p)=h(p,g) $. For example $f(17)=4 $ , $h(17,5)=13 $ and $f(73)=h(73,11)=46 $. I believe that this is true for all primes $p$ and all primitives $g$.
Now my questions are :
- Does it true that we always have $f(p)+h(p,g)=p $ or $f(p)=h(p,g) $
Is it possible to evaluate $f(p)$ and $h(p,g)$ and find the condition when does $f(p)+h(p,g)=p $ and $f(p)=h(p,g) $
I am eager to know any answer, link, or hints to this problem, thank you!!
number-theory elementary-number-theory prime-numbers primitive-roots
asked Jul 27 at 14:44
王æÂŽè¿œ
18813
While doing my research on elementary number theory, I came across the following problem which I cannot overcome: Let $p$ be an odd prime, $g$ be any primitive of $p$. Define
$$f(p)=prod_1le i <jlefracp-12j^2-i^2pmod p$$ and
$$h(p,g)=prod_1le i <jlefracp-12g^2j-g^2i pmod p .$$ What I want to know is the relationship between $f(p)$ and $h(p,g)$. I calculated the first one hundred primes and find that either $f(p)+h(p,g)=p $ or $f(p)=h(p,g) $. For example $f(17)=4 $ , $h(17,5)=13 $ and $f(73)=h(73,11)=46 $. I believe that this is true for all primes $p$ and all primitives $g$.
Now my questions are :
- Does it true that we always have $f(p)+h(p,g)=p $ or $f(p)=h(p,g) $
Is it possible to evaluate $f(p)$ and $h(p,g)$ and find the condition when does $f(p)+h(p,g)=p $ and $f(p)=h(p,g) $
I am eager to know any answer, link, or hints to this problem, thank you!!
number-theory elementary-number-theory prime-numbers primitive-roots
asked Jul 27 at 14:44
王æÂŽè¿œ
18813
edited Jul 27 at 15:24
asked Jul 27 at 14:44
王æÂŽè¿œ
18813
asked Jul 27 at 14:44
王æÂŽè¿œ
18813
asked Jul 27 at 14:44
王æÂŽè¿œ
18813
18813
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
I presume you are doing the calculations modulo $p$. In the first case
the admissible $i^2$ are the quadratic residues modulo $p$.
In the second case
the admissible $g_2i$ are also the quadratic residues modulo $p$.
Both products have the form $prod_1le i<jle m(a_j-a_i)$
where $a_1,ldots,a_m$ ($m=frac12(p-1)$) are the distinct quadratic
residues modulo $p$. But the ordering of the $a_i$ differs. If
the first product is $prod_1le i<jle m(a_j-a_i)$
and the second is $prod_1le i<jle m(b_j-b_i)$, then
$b_j=a_tau(j)$ for some permutation $tauin S_m$ and then
$prod_1le i<jle m(b_j-b_i)=textsgn(tau)
prod_1le i<jle m(a_j-a_i)$ (at least modulo $p$).
Here $textsgn(tau)$ is the sign of the permutation $tau$.
answered Jul 27 at 15:15
Lord Shark the Unknown
84.6k950111
yes , you are right. I omitted "mod p". Now I have corrected that
– çŽ‹æÂŽè¿œ
Jul 27 at 15:26
thank you very very much! Can you determine the signature of $tau$? I am waiting for you answer!!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:32
@王æÂŽè¿œ You can try to generalize the result from this question: mathoverflow.net/questions/302865
– barto
Jul 27 at 15:44
@barto Thanks for you advice.I will try to generalize that method
– çŽ‹æÂŽè¿œ
Jul 27 at 15:55
add a comment |Â
up vote
0
down vote
We are working in the field $F=Bbb F_p$ for a prime $p$.
Let $g$ be a multiplicative generator, a generator of the cyclic group
$(Bbb F_p^times, cdot)$. Then $g$ is also generating the $-1$ in the field, and of course $g^p-1=1$, $g^(p-1)/2=-1$.
Now let us consider the set $S$ of the elements $1,2,dots,(p-1)/2$ considered in $F$. These are representatives of $F^times/pm 1$. The class of $k$ is covered by $k, p-k$. Taking the squares, we obtain a list of all squares in $F$.
And also the set $T$ of the elements
$g^1,g^2,dots,g^(p-1)/2$ considered in $F$.
These are also representatives of $F^times/pm 1$.
The class of $k=g^u$ (for a suitable unique $u$) is covered by
$k=g^u, -k=g^u+(p-1)/2$. (And $u$, $u+(p-1)/2$ are not both in the list.)
Taking squares, we have as sets the equality $ j^2 : 1le jle (p-1)/2 = g^u : 1 le ule (p-1)/2 $, but for the products in the OP we also have to use the orderings of the sets, as inherited by the ones of the parametrizing indices $j$, respectively $u$.
The products differ then by the sign of the reordering.
answered Jul 27 at 15:39
dan_fulea
4,1171211
... oh, same as above, i'm definitively too slow in typing.
– dan_fulea
Jul 27 at 15:40
any way , thanks for your answer, which is also useful to me!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:57
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
I presume you are doing the calculations modulo $p$. In the first case
the admissible $i^2$ are the quadratic residues modulo $p$.
In the second case
the admissible $g_2i$ are also the quadratic residues modulo $p$.
Both products have the form $prod_1le i<jle m(a_j-a_i)$
where $a_1,ldots,a_m$ ($m=frac12(p-1)$) are the distinct quadratic
residues modulo $p$. But the ordering of the $a_i$ differs. If
the first product is $prod_1le i<jle m(a_j-a_i)$
and the second is $prod_1le i<jle m(b_j-b_i)$, then
$b_j=a_tau(j)$ for some permutation $tauin S_m$ and then
$prod_1le i<jle m(b_j-b_i)=textsgn(tau)
prod_1le i<jle m(a_j-a_i)$ (at least modulo $p$).
Here $textsgn(tau)$ is the sign of the permutation $tau$.
answered Jul 27 at 15:15
Lord Shark the Unknown
84.6k950111
yes , you are right. I omitted "mod p". Now I have corrected that
– çŽ‹æÂŽè¿œ
Jul 27 at 15:26
thank you very very much! Can you determine the signature of $tau$? I am waiting for you answer!!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:32
@王æÂŽè¿œ You can try to generalize the result from this question: mathoverflow.net/questions/302865
– barto
Jul 27 at 15:44
@barto Thanks for you advice.I will try to generalize that method
– çŽ‹æÂŽè¿œ
Jul 27 at 15:55
add a comment |Â
up vote
1
down vote
I presume you are doing the calculations modulo $p$. In the first case
the admissible $i^2$ are the quadratic residues modulo $p$.
In the second case
the admissible $g_2i$ are also the quadratic residues modulo $p$.
Both products have the form $prod_1le i<jle m(a_j-a_i)$
where $a_1,ldots,a_m$ ($m=frac12(p-1)$) are the distinct quadratic
residues modulo $p$. But the ordering of the $a_i$ differs. If
the first product is $prod_1le i<jle m(a_j-a_i)$
and the second is $prod_1le i<jle m(b_j-b_i)$, then
$b_j=a_tau(j)$ for some permutation $tauin S_m$ and then
$prod_1le i<jle m(b_j-b_i)=textsgn(tau)
prod_1le i<jle m(a_j-a_i)$ (at least modulo $p$).
Here $textsgn(tau)$ is the sign of the permutation $tau$.
answered Jul 27 at 15:15
Lord Shark the Unknown
84.6k950111
yes , you are right. I omitted "mod p". Now I have corrected that
– çŽ‹æÂŽè¿œ
Jul 27 at 15:26
thank you very very much! Can you determine the signature of $tau$? I am waiting for you answer!!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:32
@王æÂŽè¿œ You can try to generalize the result from this question: mathoverflow.net/questions/302865
– barto
Jul 27 at 15:44
@barto Thanks for you advice.I will try to generalize that method
– çŽ‹æÂŽè¿œ
Jul 27 at 15:55
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I presume you are doing the calculations modulo $p$. In the first case
the admissible $i^2$ are the quadratic residues modulo $p$.
In the second case
the admissible $g_2i$ are also the quadratic residues modulo $p$.
Both products have the form $prod_1le i<jle m(a_j-a_i)$
where $a_1,ldots,a_m$ ($m=frac12(p-1)$) are the distinct quadratic
residues modulo $p$. But the ordering of the $a_i$ differs. If
the first product is $prod_1le i<jle m(a_j-a_i)$
and the second is $prod_1le i<jle m(b_j-b_i)$, then
$b_j=a_tau(j)$ for some permutation $tauin S_m$ and then
$prod_1le i<jle m(b_j-b_i)=textsgn(tau)
prod_1le i<jle m(a_j-a_i)$ (at least modulo $p$).
Here $textsgn(tau)$ is the sign of the permutation $tau$.
answered Jul 27 at 15:15
Lord Shark the Unknown
84.6k950111
I presume you are doing the calculations modulo $p$. In the first case
the admissible $i^2$ are the quadratic residues modulo $p$.
In the second case
the admissible $g_2i$ are also the quadratic residues modulo $p$.
Both products have the form $prod_1le i<jle m(a_j-a_i)$
where $a_1,ldots,a_m$ ($m=frac12(p-1)$) are the distinct quadratic
residues modulo $p$. But the ordering of the $a_i$ differs. If
the first product is $prod_1le i<jle m(a_j-a_i)$
and the second is $prod_1le i<jle m(b_j-b_i)$, then
$b_j=a_tau(j)$ for some permutation $tauin S_m$ and then
$prod_1le i<jle m(b_j-b_i)=textsgn(tau)
prod_1le i<jle m(a_j-a_i)$ (at least modulo $p$).
Here $textsgn(tau)$ is the sign of the permutation $tau$.
answered Jul 27 at 15:15
Lord Shark the Unknown
84.6k950111
answered Jul 27 at 15:15
Lord Shark the Unknown
84.6k950111
answered Jul 27 at 15:15
Lord Shark the Unknown
84.6k950111
answered Jul 27 at 15:15
Lord Shark the Unknown
84.6k950111
84.6k950111
yes , you are right. I omitted "mod p". Now I have corrected that
– çŽ‹æÂŽè¿œ
Jul 27 at 15:26
thank you very very much! Can you determine the signature of $tau$? I am waiting for you answer!!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:32
@王æÂŽè¿œ You can try to generalize the result from this question: mathoverflow.net/questions/302865
– barto
Jul 27 at 15:44
@barto Thanks for you advice.I will try to generalize that method
– çŽ‹æÂŽè¿œ
Jul 27 at 15:55
add a comment |Â
yes , you are right. I omitted "mod p". Now I have corrected that
– çŽ‹æÂŽè¿œ
Jul 27 at 15:26
thank you very very much! Can you determine the signature of $tau$? I am waiting for you answer!!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:32
@王æÂŽè¿œ You can try to generalize the result from this question: mathoverflow.net/questions/302865
– barto
Jul 27 at 15:44
@barto Thanks for you advice.I will try to generalize that method
– çŽ‹æÂŽè¿œ
Jul 27 at 15:55
yes , you are right. I omitted "mod p". Now I have corrected that
– çŽ‹æÂŽè¿œ
Jul 27 at 15:26
yes , you are right. I omitted "mod p". Now I have corrected that
– çŽ‹æÂŽè¿œ
Jul 27 at 15:26
thank you very very much! Can you determine the signature of $tau$? I am waiting for you answer!!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:32
thank you very very much! Can you determine the signature of $tau$? I am waiting for you answer!!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:32
@王æÂŽè¿œ You can try to generalize the result from this question: mathoverflow.net/questions/302865
– barto
Jul 27 at 15:44
@王æÂŽè¿œ You can try to generalize the result from this question: mathoverflow.net/questions/302865
– barto
Jul 27 at 15:44
@barto Thanks for you advice.I will try to generalize that method
– çŽ‹æÂŽè¿œ
Jul 27 at 15:55
@barto Thanks for you advice.I will try to generalize that method
– çŽ‹æÂŽè¿œ
Jul 27 at 15:55
add a comment |Â
up vote
0
down vote
We are working in the field $F=Bbb F_p$ for a prime $p$.
Let $g$ be a multiplicative generator, a generator of the cyclic group
$(Bbb F_p^times, cdot)$. Then $g$ is also generating the $-1$ in the field, and of course $g^p-1=1$, $g^(p-1)/2=-1$.
Now let us consider the set $S$ of the elements $1,2,dots,(p-1)/2$ considered in $F$. These are representatives of $F^times/pm 1$. The class of $k$ is covered by $k, p-k$. Taking the squares, we obtain a list of all squares in $F$.
And also the set $T$ of the elements
$g^1,g^2,dots,g^(p-1)/2$ considered in $F$.
These are also representatives of $F^times/pm 1$.
The class of $k=g^u$ (for a suitable unique $u$) is covered by
$k=g^u, -k=g^u+(p-1)/2$. (And $u$, $u+(p-1)/2$ are not both in the list.)
Taking squares, we have as sets the equality $ j^2 : 1le jle (p-1)/2 = g^u : 1 le ule (p-1)/2 $, but for the products in the OP we also have to use the orderings of the sets, as inherited by the ones of the parametrizing indices $j$, respectively $u$.
The products differ then by the sign of the reordering.
answered Jul 27 at 15:39
dan_fulea
4,1171211
... oh, same as above, i'm definitively too slow in typing.
– dan_fulea
Jul 27 at 15:40
any way , thanks for your answer, which is also useful to me!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:57
add a comment |Â
up vote
0
down vote
We are working in the field $F=Bbb F_p$ for a prime $p$.
Let $g$ be a multiplicative generator, a generator of the cyclic group
$(Bbb F_p^times, cdot)$. Then $g$ is also generating the $-1$ in the field, and of course $g^p-1=1$, $g^(p-1)/2=-1$.
Now let us consider the set $S$ of the elements $1,2,dots,(p-1)/2$ considered in $F$. These are representatives of $F^times/pm 1$. The class of $k$ is covered by $k, p-k$. Taking the squares, we obtain a list of all squares in $F$.
And also the set $T$ of the elements
$g^1,g^2,dots,g^(p-1)/2$ considered in $F$.
These are also representatives of $F^times/pm 1$.
The class of $k=g^u$ (for a suitable unique $u$) is covered by
$k=g^u, -k=g^u+(p-1)/2$. (And $u$, $u+(p-1)/2$ are not both in the list.)
Taking squares, we have as sets the equality $ j^2 : 1le jle (p-1)/2 = g^u : 1 le ule (p-1)/2 $, but for the products in the OP we also have to use the orderings of the sets, as inherited by the ones of the parametrizing indices $j$, respectively $u$.
The products differ then by the sign of the reordering.
answered Jul 27 at 15:39
dan_fulea
4,1171211
... oh, same as above, i'm definitively too slow in typing.
– dan_fulea
Jul 27 at 15:40
any way , thanks for your answer, which is also useful to me!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:57
add a comment |Â
up vote
0
down vote
up vote
0
down vote
We are working in the field $F=Bbb F_p$ for a prime $p$.
Let $g$ be a multiplicative generator, a generator of the cyclic group
$(Bbb F_p^times, cdot)$. Then $g$ is also generating the $-1$ in the field, and of course $g^p-1=1$, $g^(p-1)/2=-1$.
Now let us consider the set $S$ of the elements $1,2,dots,(p-1)/2$ considered in $F$. These are representatives of $F^times/pm 1$. The class of $k$ is covered by $k, p-k$. Taking the squares, we obtain a list of all squares in $F$.
And also the set $T$ of the elements
$g^1,g^2,dots,g^(p-1)/2$ considered in $F$.
These are also representatives of $F^times/pm 1$.
The class of $k=g^u$ (for a suitable unique $u$) is covered by
$k=g^u, -k=g^u+(p-1)/2$. (And $u$, $u+(p-1)/2$ are not both in the list.)
Taking squares, we have as sets the equality $ j^2 : 1le jle (p-1)/2 = g^u : 1 le ule (p-1)/2 $, but for the products in the OP we also have to use the orderings of the sets, as inherited by the ones of the parametrizing indices $j$, respectively $u$.
The products differ then by the sign of the reordering.
answered Jul 27 at 15:39
dan_fulea
4,1171211
We are working in the field $F=Bbb F_p$ for a prime $p$.
Let $g$ be a multiplicative generator, a generator of the cyclic group
$(Bbb F_p^times, cdot)$. Then $g$ is also generating the $-1$ in the field, and of course $g^p-1=1$, $g^(p-1)/2=-1$.
Now let us consider the set $S$ of the elements $1,2,dots,(p-1)/2$ considered in $F$. These are representatives of $F^times/pm 1$. The class of $k$ is covered by $k, p-k$. Taking the squares, we obtain a list of all squares in $F$.
And also the set $T$ of the elements
$g^1,g^2,dots,g^(p-1)/2$ considered in $F$.
These are also representatives of $F^times/pm 1$.
The class of $k=g^u$ (for a suitable unique $u$) is covered by
$k=g^u, -k=g^u+(p-1)/2$. (And $u$, $u+(p-1)/2$ are not both in the list.)
Taking squares, we have as sets the equality $ j^2 : 1le jle (p-1)/2 = g^u : 1 le ule (p-1)/2 $, but for the products in the OP we also have to use the orderings of the sets, as inherited by the ones of the parametrizing indices $j$, respectively $u$.
The products differ then by the sign of the reordering.
answered Jul 27 at 15:39
dan_fulea
4,1171211
answered Jul 27 at 15:39
dan_fulea
4,1171211
answered Jul 27 at 15:39
dan_fulea
4,1171211
answered Jul 27 at 15:39
dan_fulea
4,1171211
4,1171211
... oh, same as above, i'm definitively too slow in typing.
– dan_fulea
Jul 27 at 15:40
any way , thanks for your answer, which is also useful to me!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:57
add a comment |Â
... oh, same as above, i'm definitively too slow in typing.
– dan_fulea
Jul 27 at 15:40
any way , thanks for your answer, which is also useful to me!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:57
... oh, same as above, i'm definitively too slow in typing.
– dan_fulea
Jul 27 at 15:40
... oh, same as above, i'm definitively too slow in typing.
– dan_fulea
Jul 27 at 15:40
any way , thanks for your answer, which is also useful to me!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:57
any way , thanks for your answer, which is also useful to me!!
– çŽ‹æÂŽè¿œ
Jul 27 at 15:57
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%2f2864445%2fhow-to-evaluate-prod-1-le-i-j-le-fracp-12j2-i2-pmod-p%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