Restricted linear congruences and their significance in computer science and geometry
In this talk, using properties of Ramanujan sums and of the discrete Fourier transform of arithmetic functions, we give an explicit formula for the number of solutions of the linear congruence a1x1+...+akxk ≡ b mod n, with gcd(xi, n)=ti (1 ≤ i ≤ k), where a1, t1, ..., ak, tk, b, n (n ≥ 1) are arbitrary integers. As a consequence, we derive necessary and sufficient conditions under which the above restricted linear congruence has no solutions. The number of solutions of these kinds of congruences was first considered by Rademacher in 1925 and Brauer in 1926, in the special case of ai=ti=1 (1 ≤ i ≤ k). Since then, this problem has been studied, in several other special cases, in many papers. The problem is very well-motivated and has found intriguing applications in several areas of mathematics, computer science, and physics, and there is promise for more applications/implications in these or other directions. We also discuss applications to universal hashing (an area of significant importance in computer science) and from there to cryptography. We even go further and discuss applications in geometry. Specifically, we give an explicit formula for the number of surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group (which has important applications in combinatorics and physics). As a consequence, we obtain an `equivalent' form of the famous Harvey's theorem on the cyclic groups of automorphisms of compact Riemann surfaces.