FWIW, this wikipedia article makes the same claim for p=4k+3, which uses the term "modulus" instead of "representative": https://en.wikipedia.org/wiki/Trigonometry_in_finite_fields The "modulus" of an element a+jb in {a+jb; a,b in GF(q); j^2=-1}, where p=4k+3, is a+jb = |a^2+b^2| = +sqrt(a^2+b^2). At 08:28 AM 8/26/2017, Henry Baker wrote:
How about this weird form of division (in maxima):
qdivide(m,n):=block([q,r,q1,r1], q:floor(m/n), r:m-q*n, /* r is non-negative */ if is(jacobi(r,n)=-1) then (q1:q+1,r1:r-n) else (q1:q,r1:r), [q1,r1]);
e.g.,
(%i25) qdivide(1,19); (%o25) [0, 1] (%i26) qdivide(2,19); (%o26) [1, - 17] (%i27) qdivide(3,19); (%o27) [1, - 16] (%i28) qdivide(4,19); (%o28) [0, 4] (%i29) qdivide(5,19); (%o29) [0, 5] (%i30) qdivide(6,19); (%o30) [0, 6] (%i31) qdivide(7,19); (%o31) [0, 7] (%i32) qdivide(8,19); (%o32) [1, - 11] (%i33) qdivide(9,19); (%o33) [0, 9] (%i34) qdivide(10,19); (%o34) [1, - 9] (%i35) qdivide(11,19); (%o35) [0, 11] (%i36) qdivide(12,19); (%o36) [1, - 7] (%i37) qdivide(13,19); (%o37) [1, - 6] (%i38) qdivide(14,19); (%o38) [1, - 5] (%i39) qdivide(15,19); (%o39) [1, - 4] (%i40) qdivide(16,19); (%o40) [0, 16] (%i41) qdivide(17,19); (%o41) [0, 17] (%i42) qdivide(18,19); (%o42) [1, - 1] (%i43) qdivide(19,19); (%o43) [1, 0]
If we utilize this form of division for base conversion to a prime base p=3(mod 4), we automatically get a representation whose digits are +-r, where r is a quadratic residue (mod p).
One obvious property: perfect +- symmetry: negation means negating every digit.
Questions:
Does anything interesting happen when this form of division is used in other places -- e.g., gcd algorithms?
Does this type of division induce a slightly different "norm" s.t. the norm of the remainder is strictly < the norm of the divisor?
I suspect that there is a close relationship with division in the Gaussian integers, but I haven't checked this yet.