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.