elementary question

[kurtulmehtap]

In the article http://library.uwinnipeg.ca/people/d...e_numbers.html
the congruence (4) states
c ≡ q^2 − 2 (mod 256) (p > 8) where c*q^2≡2^q-1

and in the next paragraph it is stated that the congruence (4) is solved by
c ≡ ±2q −(−1)(q^2−1)/16∙32 + 29 (mod 256)

Can someone explain how we did obtain
±2q −(−1)(q^2−1)/16∙32 + 29 (mod 256)?

[R.D. Silverman]

Originally Posted by kurtulmehtap

In the article http://library.uwinnipeg.ca/people/d...e_numbers.html
the congruence (4) states
c ≡ q^2 − 2 (mod 256) (p > 8) where c*q^2≡2^q-1

and in the next paragraph it is stated that the congruence (4) is solved by
c ≡ ±2q −(−1)(q^2−1)/16∙32 + 29 (mod 256)

Can someone explain how we did obtain
±2q −(−1)(q^2−1)/16∙32 + 29 (mod 256)?

Perhaps we have a copying error here?
16^-1 does not exist mod 256........


Is 16*32 supposed to be (16*32)?? It's inverse doesn't exist
either..

[TheMawn]

In the article, what is the meaning of the three vertical bars?

I.e. (A − 1) ||| (B + 1)

[Batalov]

Originally Posted by kurtulmehtap

...the congruence (4) is solved by
c ≡ ±2q −(−1)(q^2−1)/16∙32 + 29 (mod 256)

Can someone explain how we did obtain
±2q −(−1)(q^2−1)/16∙32 + 29 (mod 256)?

It is c ≡ ±2q −(−1)^{(q^2−1)/16}∙32 + 29 (mod 256).

Note that (−1)^{(q^2−1)/8} = legendre(2|q). Hmmm...
Well, we only have q ≡ ±1 (mod 8), so (2|q) = 1 and sqrt of it could be ±1.

[Batalov]

Originally Posted by TheMawn

In the article, what is the meaning of the three vertical bars?

I.e. (A − 1) ||| (B + 1)

Read the article?
This is defined in the first lemma.

[kurtulmehtap]

Originally Posted by Batalov

It is c ≡ ±2q −(−1)^{(q^2−1)/16}∙32 + 29 (mod 256).

Note that (−1)^{(q^2−1)/8} = legendre(2|q). Hmmm...
Well, we only have q ≡ ±1 (mod 8), so (2|q) = 1 and sqrt of it could be ±1.

Thanks,
I got to the step where
(−1)^{(q^2−1)/8} = legendre(2|q).
but still can not figure out where c ≡ ±2q −(−1)^{(q^2−1)/16}∙32 + 29 (mod 256). comes from.

[Batalov]

It is possible that the author simply mixed and matched this with a value table (which is easy). It can be probably written in other ways. It is a shorthand to replace an ugly table.

Similarly, some people write that e.g. Gaussian-Mersenne numbers are (with m=(p+1)/2)):
2^p − 2^m +1 when p ≡ ±1 (mod 8) and 2^p + 2^m +1 for other odd p,
and some roll this into one formula
2^p −(−1)^{(p^2−1)/8} ∙ 2^m +1
and some use
2^p − cos(p*Pi/4)*2^(1+p/2) + 1
It's hard to say which one is more elegant.

[CRGreathouse]

Originally Posted by Batalov

It's hard to say which one is more elegant.

It's easy to say which is least elegant. cos has no place in these sorts of equations, that's needless abuse of transcendentals.

[kurtulmehtap]

Originally Posted by Batalov

It is possible that the author simply mixed and matched this with a value table (which is easy). It can be probably written in other ways. It is a shorthand to replace an ugly table.

Similarly, some people write that e.g. Gaussian-Mersenne numbers are (with m=(p+1)/2)):
2^p − 2^m +1 when p ≡ ±1 (mod 8) and 2^p + 2^m +1 for other odd p,
and some roll this into one formula
2^p −(−1)^{(p^2−1)/8} ∙ 2^m +1
and some use
2^p − cos(p*Pi/4)*2^(1+p/2) + 1
It's hard to say which one is more elegant.

Thanks for your help...