Math 365. Number Theory. Spring 1998. Fri, Mar 13, 1998 No limitation on the use of (super)computers, books, notes. Write the pledge. 1. Denote by K the set of positive integers n whose decimal representation of n^2 łends˛ with n. For example, the numbers 1, 5, 6, 25 and 76 lie in K. (a) List all numbers in K <1000000; (b) List all 8-digit numbers in K; (c) Prove that that there are at most two 300-digit numbers in K. 2. Let p„2 be a prime. (A) Prove that if p = 3k+2 then x^3 = a has a solution in Z_p for every a in Z_p. (B) Prove that if p = 3k+1 then x^3 = a has no solution in Z_p for some a in Z_p. 3. For an odd prime p, denote by a(p) the number of quadratic residues x, p/4 < x < p/3. Prove that for all large enough primes p the inequality p/25 < a(p) < p/20 takes place. 4. Given a prime p>4. Find the number of solutions (x,y) of x^2+y^2=3; x, y in Z_p. 5. Solve x^2=1 (mod n), where n = 99221377 (i.e., in Z_n). (a) Find the number of solutions (b) List the solutions. WARNING. The above n is not prime. Each problem 30 pts. SOLUTIONS. Solution of 1(a). A d-digit number x lies in K if and only if x^2-x=x(x-1)=0 mod(10^d). x is a k-digit number if and only if 10^(d-1)<=x<10^d. We collect solutions in the array s. ___________________________________________ >> >>s=[]; >>% finding d-digit solutions with d=1 >>d=1; x=10^(d-1):(10^d-1); snew=x(mod(x.^2-x,10^d)==0) snew = 1 5 6 >>s=[s snew]; >>% finding d-digit solutions with d=2 >>d=2; x=10^(d-1):(10^d-1); snew=x(mod(x.^2-x,10^d)==0) snew = 25 76 >>s=[s snew]; >>% finding d-digit solutions with d=3 >>d=3; x=10^(d-1):(10^d-1); snew=x(mod(x.^2-x,10^d)==0) snew = 376 625 >>s=[s snew]; >>% finding d-digit solutions with d=4 >>d=4; x=10^(d-1):(10^d-1); snew=x(mod(x.^2-x,10^d)==0) snew = 9376 >>s=[s snew]; >>s s = Columns 1 through 6 1 5 6 25 76 376 Columns 7 through 8 625 9376 >>% finding d-digit solutions with d=5 >>d=5; x=10^(d-1):(10^d-1); snew=x(mod(x.^2-x,10^d)==0) snew = 90625 >>s=[s snew]; >>% finding d-digit solutions with d=6 >>d=6; x=10^(d-1):(10^d-1); snew=x(mod(x.^2-x,10^d)==0) ??? Out of memory. Type HELP MEMORY for your options. Error in ==> Macintosh HD:MATLAB 5:Toolbox:matlab:elfun:mod.m On line 36 ==> z(m) = x(m) - floor(x(m)./y(m)).*y(m); >>% the array is too big - one should partition it >>x=100000:500000; snew=x(mod(x.^2-x,10^d)==0) snew = 109376 >>s=[s snew]; >>x=500001:999999; snew=x(mod(x.^2-x,10^d)==0) snew = 890625 >>s=[s snew]; >>% THUS THE LIST OF SOLUTIONS TO 1(a) IS >>disp(s) Columns 1 through 6 1 5 6 25 76 376 Columns 7 through 11 625 9376 90625 109376 890625 >>% Thus there are 11 solutions >>disp(num2str(s)) 1 5 6 25 76 376 625 9376 90625 109376 890625 ________________________________________________________ ________________________________________________________ Solution of 1(b). Have to find solutions x^2-x=x(x-1)=0 mod(10^8). The above is true if and only if it is true mod a=5^8 and b=2^8 since (a,b)=1. Modulu each of these numbers we have 2 sols: 0, 1. Thus by Chinese Rem Thm we may have four solutions corresponding to the pairs (0,0),(1,1),(1,0),(0,1). The first two lead to the solutions 0, 1 which fail to be 8-digit numbers. The other two can be obtained in two ways. The easiest way is using my chin function. >>chin(1,5^8,0,2^8) ans = 87109376 100000000 >>s=ans(1) s = 87109376 >>chin(0,5^8,1,2^8) ans = 12890625 100000000 >>s=[s ans(1)] s = 87109376 12890625 The above are the only two solutions for 1(b). ________________________________________________________ The alternative way to get these solutions is to observe that mod 10^6 these solutions must be 109376 and 890625, see 1(a). Thus to get a solution corresponding to 109376 we do the following >>x=109376:1000000:100000000; >>snew=x(mod(x.^2-x,10^8)==0) snew = 87109376 and exactly the same way we obtain the other solution. >>x=890625:1000000:100000000; >>snew=x(mod(x.^2-x,10^8)==0) snew = 12890625 __________________________________________________ __________________________________________________ Solution of 1(c). See the beginning of Solution 1(b). (Also explained in class.) __________________________________________________ __________________________________________________ 5. Solve x^2=1 (mod n), where n = 99221377 (i.e., in Z_n). (a) Find the number of solutions (b) List the solutions. ___________________________________________________ Solution of 5. >>x=99221377 x = 99221377 >>p=factor(x) p = 9949 9973. Modulo each p we have 2 sols, thus total number of sols is 4. Two sols, 1 and -1, are obvious. The other two are obtained by using my chin function. >>x=chin(-1,9949,1,9973) x = 8267618 99221377 >>chin(1,9949,-1,9973) ans = 90953759 99221377 >>x(2)=ans(1); >>x x = 8267618 90953759 >>% let check the solutions >>mod(x.^2,99221377) ans = 1 1 ANSWER: 4 solutions mod 99221377: 1, -1=99221376, 8267618, 90953759. _________________________________________________ Problems 2, 3, 4 are explained in class