250 PROBLEMS IN ELEMENTARY NUMBER …

1 250 problems in elementary number theory WACLAW SIERPINSKI ISBN ().444.()()()71 2 250 PROBLEMS , in ELEMENTARY NUMBER theory .-WACLAW SIERPINSKI " 250 problems in elementary number theory " presents PROBLEMS and their solutions in five specific areas of this branch of mathe-matics: divisibility of numbers, relatively prime numbers, arithmetic progressions, prime and composite numbers, and Diophantic equations. There is, in addition, a section of miscellaneous PROBLEMS . Included are PROBLEMS on several levels of difficulty-some are relatively easy, others rather complex, and a NUMBER so abstruse that they originally were the subject of scientific research and their solutions are of comparatively recent date. All of the solutions are given thoroughly and in detail; they contain information on possible generaliza-tions of the given problem and further indicate unsolved PROBLEMS associated with the given problem and solution.

2 This ancillary textbook is intended for everyone interested in NUMBER theory . It will be of especial value to instructors and students both as a textbook and a source of reference in mathematics study groups. 250 problems in elementary number theory Modern Analytic and Computational Methods in Science and Mathematics A GROUP OF MONOGRAPHS AND ADVANCED TEXTBOOKS Richard Bellman, EDITOR University of Southern California Published 1. R. E. Bellman, R. E. Kalaba, and Marcia C. Prestrud, Invariant Imbedding and Radiative Transfer in Slabs of Finite Thickness, 1963 2. R. E. Bellman, Harriet H. Kagiwada, R. E. Kalaba, and Marcia C. Prestrud, Invariant Imbedding and Time-Dependent Transport Processes, 1964 3. R. E. Bellman and R. E. Kalaba, Quasilinearization and Nonlinear Bounda-ry-Value PROBLEMS , 1965 4.

3 R. E. Bellman, R. E. Kalaba, and Jo Ann Lockett, Numerical Inversion of the Laplace Transform: Applications to Biology, Economics, Engineering, and Physics, 1966 5. S. G. Mikhlin and K. L. Smolitskiy, Approximate Methods for Solution of Differential and Integral Equations, 1967 6. R. N. Adams and E. D. Denman, Wave Propagation and Turbulent Media, 1966 7. R. L. Stratonovich, Conditional Mar-kov Processes and Their Application to the theory of Optimal Control, 1968 8. A. G. Ivakhnenko and V. G. Lapa, Cybernetics and Forecasting Techniques, 1967 9. G. A. Chebotarev, Analytical and Numerical Methods of Celestial Me-chanics, 1967 10. S. F. Feshchenko, N. I. Shkil', and L. D. Nikolenko, Asymptotic Methods in the theory of Linear Differential Equa-tions, 1967 11. A. G. Butkovskiy, Distributed Control Systems, 1969 12.

4 R. E. Larson~ State Increment Dy-namic Programming, 1968 13. J. Kowalik and M. R. Osborne, Methods for Unconstrained Optimiza-tion PROBLEMS , 1968 14. S. J. Yakowitz, Mathematics of Adaptive Control Processes, 1969 15. S. K. Srinivasan, Stochastic theory and Cascade Processes, 1969 16. D. U. von Rosenberg, Methods for the Numerical Solution of Partial Dif-ferential Equations, 1969 17. R. B. Banerji, theory of PROBLEMS Solving: An Approach to Artificial In-telligence, 1969 18. R. Lattes and Lions, The Method of Quasi-Reversibility: Applications to Partial Differential Equations. Translated from the French edition and edited by Richard Bellman, 1969 19. D. G. B. Edelen, Nonlocal Variations and Local Invariance of Fields, 1969 20. J. R. Radbill and G. A. McCue, Quasilinearization and Nonlinear Pro-blems in Fluid and Orbital Mechanics, 1970 26.

5 W. Sierphlski. 250 PROBLEMS in Elemen-tary NUMBER theory , 1970 In Preparation 21. W. Squire, Integration for Engineers and Scientists 22. T. Pathasarathy and T. E. S. Ragha-van, Some Topics in Two-Person Games 23. T. Hacker, Flight Stability and Control 24. D. H. Jacobson and D. Q. Mayne, Differential Dynamic Processes 25. H. Mine and S. Osaki, Markovian Decision Processes 27. E. D. Denman. Coupled Modes in Plasms. Elastic Media. and Parametric Amplifiers 28. F. A. Northover, Applied Diffraction theory 29. G. A. Phillipson. Identification of Distributed Systems 30. D. H. Moore, Heaviside Operational Calculus: An ELEMENTARY Foundation 250 problems in elementary number theory by W. SIERPINSKI Polish Academy of Sciences AMERICAN ELSEVIER PUBLISHING COMPANY, INC. NEW YORK PWN-POLISH SCIENTIFIC PUBLISHERS WARSZAWA 1970 AMERICAN ELSEVIER PUBLISHING COMPANY, INC.

6 52 Vanderbilt Avenue, New York, 10017 ELSEVIER PUBLISHING COMPANY, LTD. Barking, Essex, England ELSEVIER PUBLISHING COMPANY 335 Jan Van Galenstraat, Box 211 Amsterdam, The Netherlands Standard Book NUMBER 444-00071 2 Library of Congress Catalog Card NUMBER 68 17472 COPYRIGHT 1970 BY PANSTWOWE WYDAWNIcrwO NAUKOWE WARSZAWA (pOLAND) MIODOWA 10 All rights reserved. No part of this publication may be reproduced. stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher, American Elsevier Publishing Company, Inc., 52 Avenue, New York, N. Y. 10017. PRINTED IN POLAND CONTENTS PROBLEMS Solutions I. Divisibility of Numbers . 1 23 II. Relatively Prime Numbers 3 35 III.

7 Arithmetic Progressions 4 40 IV. Prime and Composite Numbers. 6 48 V. Diophantine Equations 11 73 VI. Miscellanea . 18 101 References 122 Name Index 125 VII PROBLEMS I. DIVISIBILITY OF NUMBERS 1. Find all positive integers n such that n2+ 1 is divisible by n+ 1. 2. Find all integers x #= 3 such that x-3Ix3-3. 3. Prove that there exists infinitely many positive integers n such that 4n2+ 1 is divisible both by 5 and 13. 4. Prove that for positive integer n we have 16913311+3-26n-27. S. Prove that 191 226t+2 +3 for k = 0, 1, 2, .. 6. Prove the theorem, due to Kraitchik, asserting th~t 13127 +37 . 7. Prove that 8. Prove that for positive integer m and a > 1 we have ( a"'-l ) a-I ,a-I = (a-I,m). 9. Prove that for every positive integer n the NUMBER 3(15+25+ .. +nS) is divisible by 13+23+.

8 +n3 10. Find all integers n > 1 such that 1 "+2"+ .. +(n-l)" is divisible by n. 11. For positive integer n, find which of the two numbers an = 22n+1_ -2"+1+1 and b" = 2211+1+2,,+1+1 is divisible by 5 and which is not. 12. Prove that for every positive integer n there exists a positive integer x such that each of the terms of the infinite sequenc~ x+ I, xx+ 1, xxx + 1, .. is divisible by n. 13. Prove that there exists infinitely many positive integers n such that 1 2 250 PROBLIMS IN NUMBER theory for every even x none of the terms of the sequence x-~ + 1, xxX + 1, / + 1, '" is divisible by n. 14. Prove that for positive integer n we have n21(n+l)"-1. 15. Prove that for positive integer n we have (2"_1)212(2"-1)"_1. 16. Prove that there exist infinitely many positive integers n such that nI2"+I; find all such prime numbers.

9 17*. Prove that for every positive integer a > 1 there exist infinitely many positive integers n such that nla" + 1. 18*. Prove that there exist infinitely many positive integers n such that nI2"+2. 1~. Find all positive integers a for which a10+ 1 is divisible by 10. 20*. Prove that there are no integers n > 1 for which nI2"-1. 20a. Prove that there exist infinitely many positive integers n such that nI2"+1. 21. Find all odd n such that n13" + 1. 22. Find all positive integers n for which 3In2"+ 1. 23. Prove that for every odd prime p there exist infinitely many positive integers n such that pln2"+ 1. 24. Prove that for every positive integer n there exist positive integers x> nand y such that ,xXI>" but x =1= y. 25*. Prove that for odd n we have nI2"!-1. 26. Prove that the infinite sequence 2"-3 (n = 2,3,4.)

10 Contains in-finitely many terms divisible by 5 and infinitely many terms divisible by 13, but contains no term divisible by 5 13. 27*. Find two least composite numbers n such that nI2"-2 and nI3"-3. 28*. Find the least positive integer n such that nI2"-2 but n,r 3"-3. 29. Find the least integer n such that n,r 2"-2 but nI3"-3. 30. For every positive integer a, find a composite NUMBER n such that nla"-a. * An asterisk attached to the NUMBER of a problem indicates that it is more dif-ficult. PROBLIMS 3 31. Prove that if for some integers a, b, c we have 9Ia3+b3+c3, then at least one of the numbers a, b, c is divisible by 3. 32. Prove tbat if for positive integers ak (k = 1, 2, 3, 4, 5) we have 9Ia~+a~+a~+a:+a~, then 31a1 a2a3a4Q,. 33. Prove that if x, y, z are positive integers such that (x, y) = 1 and r+r = Z4, then 7lxy; show that the condition (x, y) = 1 is necessary.