congruence {elliptic}R Documentation

Solves mx+by=1 for x and y


Solves the Diophantine equation mx+by=1 for x and y. The function is named for equation 57 in Hardy and Wright.


congruence(a, l = 1)



Two element vector with a=c(m,n)


Right hand side with default 1


In the usual case of (m,n)=1, returns a square matrix whose rows are a and c(x,y). This matrix is a unimodular transformation that takes a pair of basic periods to another pair of basic periods.

If (m,n)\neq 1 then more than one solution is available (for example congruence(c(4,6),2)). In this case, extra rows are added and the matrix is no longer square.


This function does not generate all unimodular matrices with a given first row (here, it will be assumed that the function returns a square matrix).

For a start, this function only returns matrices all of whose elements are positive, and if a is unimodular, then after diag(a) <- -diag(a), both a and -a are unimodular (so if a was originally generated by congruence(), neither of the derived matrices could be).

Now if the first row is c(1,23), for example, then the second row need only be of the form c(n,1) where n is any integer. There are thus an infinite number of unimodular matrices whose first row is c(1,23). While this is (somewhat) pathological, consider matrices with a first row of, say, c(2,5). Then the second row could be c(1,3), or c(3,8) or c(5,13). Function congruence() will return only the first of these.

To systematically generate all unimodular matrices, use unimodular(), which uses Farey sequences.


Robin K. S. Hankin


G. H. Hardy and E. M. Wright 1985. An introduction to the theory of numbers, Oxford University Press (fifth edition)

See Also



M <- congruence(c(4,9))

o <- c(1,1i) -,maxiter=840)  #should be zero

[Package elliptic version 1.4-0 Index]