Classes of Functions Representation of Integers by Functions

CLASSES OF FUNCTIONS. REPRESENTATION OF INTEGERS BY FUNCTIONS Equivalent Functions and Equations.—The problem to find all solutions of in integers is equivalent to that for 41, which is derived from the first equation by the substitution x= X+ 2Y, y= Y. The discussion is not more difficult if we start with any substitution Hence to any pair of integers x and y corresponds a single pair of integers X and Y, and conversely by (I). Let the substitution (I) replace the function f(x, y) by F(X, Y). Then if g is any given integer, the integral solutions of f = g are put into one-to. one correspondence with those of F=g by the substitution (I), so that the problem to find all solutions of f= g in integers is evidently equivalent to that for F= g. We therefore need only treat one of the infinitely many equivalent equations.

These two functions f and F are called equivalent. Let F(X, Y) become G(u, v) when we apply the new substitution with integral coefficients whose determinant is +1. If we eliminate X and Y between the four equations (I) and (2), we evidently obtain equations of the form x=Au+Bv, y=Cu+Dv. (3) The coefficients are seen to be integers whose determinant is unity. This substitution (3) is called the product of the sub stitutions (I) and (2) taken in that order. Since (I) replaces f by F, and (2) replaces F by G, evidently (3) replaces f by G. This proves that if f and G are both equivalent to F, they are equivalent to each other. Hence all the functions which are equiv alent to a given one f form a class of functions any two of which are equivalent. It is easy to extend this discussion for two vari ables x and y to any number of variables.

When f(x, y, • • •) = g has integral solutions, g is said to be represented by f. In case x, y, • • . have no common factor > I, g is properly represented by f. For example, whence 29 is properly represented by Positive Binary Quadratic Forms.—The function is called a binary quadratic form and is denoted by (a, b, c). Its discriminant is — 4ac . Two equivalent forms have the same discriminant.

Let A be properly represented by f, whence f= A for relatively prime integers x=r, y=s. As shown above, there exist two in tegers t and u such that rt —su= I. The substitution whose determinant is unity, replaces f by an equivalent form in which the coefficient of is A.

Let a> o and let the discriminant of f be a negative number —LI. Then Oaf= shows that f is positive for all real numbers x and y not both zero. Hence f is called a positive form (see ALGEBRAIC FORMS). Let A be the least positive integer which is represented by this f. If f=A when x =r, y=s, and if r and s have a common factor d> I, then when x=r/d, y=s/d, which contradicts the definition of A as least. Thus A is properly represented by f. As shown above, f is equivalent to some form g= (A, (3, 7) with A as first coefficient. The substitution x= y= Y replaces g by F = (A, B, C), where B = 2nA. Evidently the integer n may be chosen so that — A < B < A. Since C is represented by F, Cis not less than the minimum A . In case C= A, the substitution x= — Y, y= X, whose determinant is unity, replaces F by (A, A). This proves that every positive form is equivalent to a reduced form (A, B, C) in which Then Hence if A is given, there is a limited number of positive integral values of A. The same is now true for B by (4). Each pair of integers A and B determines at most one integer C for which 4AC=A+W. Hence there is only a finite number of positive We are now in a position to discuss one of the most useful theorems in the theory of numbers: If a is any positive integer not of the form 4k(8n+7), then a is a sum of three squares having no common factor >I. Complicated proofs were,first given by Legendre in 1798 and by Gauss in i8oi. The simplest proof is that by Dirichlet in 185o. It employs a positive form (I) whose determinant d is unity. Take s= 1, t=o. Then d= b, where A denotes Let a be double an odd integer. There are infinitely many primes in any arithmetical progression whose first term and common difference are relatively prime. Hence we can choose a positive integer 1 so that b=4ald-a—i is a prime. Take A =4/+I. Then (—A/b)= +1. Hence there is an integer r such that is an integer c. The resulting positive form (I) of determinant unity must be equivalent to by our previous theorem. Hence X = ax+ • • • , Ox+ • • • , Z=yx+ • • • have integral coefficients whose determinant is unity. Hence a = where a, 0, y are integers with no common factor > i. The proof is similar for the remaining numbers a.