Art. 102. To determine whether a number is prime or composite. Rule. If the number is found in the Table of Prime Numbers, it is prime. If it does not exceed 2207, and is not found in the table, it is composite. If it exceeds 2207, and ends in 0, 2, 4, 5, 6, or 8, it is composite. If it exceeds 2207, and ends in 1, 3, 7, or 9, divide it by the successive primes except 1. If an exact divisor is thus found, the number is composite; if an exact divisor is not found, and the quotient is less than the divisor, the number is prime. NOTE 1.-When the quotient is less than the divisor, and not exact, it shows, First, that no number greater than the trial divisor (except the number itself,) is a divisor, since its quotient, (which would be less than the present trial divisor,) would then be a divisor; and this cannot be, because taking the successive primes as trial divisors has excluded it. Second, that no number less than the trial divisor, except 1 is a divisor, since, if prime, it has been tried, and, if composite, its prime factors (which would be divisors, because every number is a divisor of all its multiplies,) have been tried. NOTE 2. The foregoing rule and table will determine the primes as far as the square of the last number in the table, namely, 2207 × 2207, 4870849. Art. 103. Factoring is finding the factors of a number. It is often called resolving a number into its factors. Proposition. Every number equals the product of its prime factors. DEMONSTRATION.-If all the factors are prime, the proposition is clearly true. If some of the factors are composite, those factors are produced by factors either prime or composite. If by com posite, the composite factors are again resolvable into factors either prime or composite. Thus, at the last possible resolution, all the factors must be prime numbers. In which the factors of 1152 are all prime. COROLLARY.-A number is divisible only by its prime factors, or by some product of them. Art. 104. To find the prime factors of a number. Ex. 1. What are the prime factors of 805? WRITTEN PROCESS. 5) 8 0 5 7) 16 1 23 Ans. 5, 7, 23. EXPLANATION. Since the number ends with 5, we see that 5 is a prime factor of it. (Art. 100, Prop. 12.) Hence dividing by 5, we resolved 805 into 5 X 161. As 161 ends in 1, it is not divisible by 2, 4, 5, or 6. Trying 3, we find it not a divisor, or factor. Trying 7, we find it is a factor, resolving 161 into 7 X 23. But 23 is are 5, 7, and 23. prime. Therefore, the prime factors of 805 Rule.-Divide the given number by any prime number, except 1, which is contained in it without a remainder. Divide the quotient, if it is composite, in the same manner. Do thus till a quotient is found which is a prime number. The last quotient and all the divisors are the prime factors of the given number. PROOF.-Multiply together all the prime factors. The product should be the given number. NOTE 1.-The judgment of the student must be guided by the facts stated in the propositions given in Art. 100, on divisibility of integers. When the prime factors are small, such as 2, 3, 5, 7, or 11, they can be readily found by the foregoing rule; but, when they are large, the process is often tedious, because of the number of trials which must be made. When the number is even we should divide by 2, so continuing till the quotient is odd. Then we can rapidly try the smaller odd prime numbers. NOTE 2.-To avoid waste of time in making trials, the student can use a factor table. That given on the next two pages contains all the composite numbers less than 10000 which are not divisible by 2, 3, 5, 7, or 11. Their least prime factors are placed at their right-hand in small figures. To use the table, proceed by the following: Rule. First find all the prime factors of the given number which are less than 13. If the last quotient is contained in the table, it is a composite number, and its least prime factor is in small figures at the right. Divide by this prime factor. If the quotient thus obtained is in the table, proceed as before. EXAMPLES FOR PRACTICE. 2. Find the prime factors of 9971. Ans. 13, 13, 59. NOTE. Finding 9971 in the factor tables, we divide by its least prime factor, 13, there given; then, finding the quotient, 767, in the factor table, we divide by its least prime factor. Since the quotient, 59, is prime, the prime factors of 9971 are 13, 13, and 59. 299 13 1147 31 169 13 1079 13 1751 17 2353 13 2951 13 3481 59 4061 31 4579 19 5129 23 221 13 1081 23 1763 41 2363 17 2977 13 3497 13 4063 17 4589 13 5141 53 247 13 1121 19 1769 29 2369 23 2983 19 3503 31 4069 13 4601 43 5143 37 289 17 1139 17 1781 13 2407 29 2987 29 3523 13 4087 61 4607 17 5149 19 1807 13 2413 19 2993 41 3551 53 4097 17 4619 31 5161 13 323 17 1157 13 1817 23 2419 41 3007 31 3569 43 4117 23 4633 41 5177 31 361 19 1159 19 1819 17 2449 31 3013 23 3587 17 4121 13 4661 59 5183 71 377 13 1189 29 1829 31 2461 23 3029 13 3589 37 4141 41 4667 13 5191 29 391 17 1207 17 1843 19 2479 37 3043 17 3599 59 4163 23 4681 31 5207 41 403 13 1219 23 1849 43 2483 13 3053 43 3601 13 4171 43 4687 43 5213 13 437 19 1241 17 1853 17 2489 19 3071 37 3611 23 4181 37 4693 13 5219 17 481 13 1247 29 1891 31 2491 47 3077 17 3629 19 4183 47 4699 37 5221 23 493 17 1261 13 1909 23 2501 41 3097 19 3649 41 4187 53 4709 17 5239 13 527 17 1271 31 1919 19 2507 23 3103 29 3653 13 4189 59 4717 53 5249 29 529 23 1273 19 1921 17 2509 13 3107 13 3667 19 4199 13 4727 29 5251 59 533 13 1313 13 1927 41 2533 17 3127 53 3679 13 4223 41 4747 47 5263 19 551 19 1333 31 1937 13 2537 43 3131 31 3683 29 4237 19 4757 67 5267 23 559 13 1339 13 1943 29 2561 13 3133 13 3713 47 4247 31 4769 19 5287 17 589 19 1343 17 1957 19 2567 17 3139 43 3721 61 4267 17 4771 13 5293 67 611 13 1349 19 1961 37 2573 31 3149 47 3737 37 4303 13 4777 17 5311 47 629 17 1357 23 1963 13 2581 29 3151 23 3743 19 4307 59 4811 17 5317 13 667 23 1363 29 2021 43 2587 13 3161 29 3749 23 4309 31 4819 61 5321 17 689 13 1369 37 2033 19 2599 23 3173 19 3757 13 4313 19 4841 47 5329 73 697 17 1387 19 2041 13 2603 19 3193 31 3763 53 4321 29 4843 29 5339 19 703 19 1391 13 2047 23 2623 43 3197 23 3781 19 4331 61 4847 37 5353 53 713 23 1403 23 2059 29 2627 37 3211 13 3791 17 4343 43 4849 13 5359 23 731 17 1411 17 2071 19 2641 19 3233 53 3799 29 4351 19 4853 23 5363 31 767 13 1417 13 2077 31 2669 17 3239 41 3809 13 4369 17 4859 43 5371 41 779 19 1457 31 2117 29 2701 37 3247 17 3811 37 4379 29 4867 31 5377 19 793 13 1469 13 2119 13 2743 13 3263 13 3827 43 4381 13 4883 19 5389 17 799 17 1501 19 2147 19 2747 41 3277 29 3841 23 4387 41 4891 67 5429 61 817 19 1513 17 2159 17 2759 31 3281 17 3859 17 4393 23 4897 59 5447 13 841 29 1517 37 2171 13 2771 17 3287 19 3869 53 4399 53 4901 13 5459 53 851 23 1537 29 2173 41 2773 47 3293 37 3887 13 4427 19 4913 17 5461 43 871 13 1541 23 2183 37 2809 53 3317 31 3893 17 4429 43 4927 13 5473 13 893 19 1577 19 2197 13 2813 29 3337 47 3901 47 4439 23 4979 13 5491 17 899 29 1591 37 2201 31 2831 19 3341 13 3937 31 4453 61 4981 17 5497 23 901 17 1633 23 2209 47 2839 17 3349 17 3953 59 4469 41 4997 19 5513 37 923 13 1643 31 2227 17 2867 47 3379 31 3959 37 4471 17 5017 29 5539 29 943 23 1649 17 2231 23 2869 19 3383 17 3961 17 4489 67 5029 47 5543 23 949 13 1651 13 2249 13 2873 13 3397 43 3973 29 4511 13 5041 71 5549 31 961 31 1679 23 2257 37 2881 43 3401 19 3977 41 4531 23 5053 31 5561 67 989 23 1681 41 2263 31 2899 13 3403 41 3979 23 4537 13 5057 13 5567 19 1003 17 1691 19 2279 43 2911 41 3419 13 3991 13 4541 19 5063 61 5587 37 1007 19 1703 13 2291 29 2921 23 3427 23 4009 19 4553 29 5069 37 5597 29 102713 1711 29 2323 23 2923 37 3431 47 4031 29 4559 47 5083 13 5603 13 1037 17 1717 17 2327 13 2929 29 3439 19 4033 37 4573 67 5111 19 5609 71 1073 29 1739 37 2329 17 2941 17 3473 23 4043 13 4577 23 5123 47 5611 31 FACTOR TABLE. No. Fac. No. Fac. 8549 83 9071 47 No. Fac. No. Fac. No. Fac. No. Fac. No. Fac. No. Fac. 5617 41 6119 29 6631 19 7141 37 7627 29 8077 41 5627 17 6137 17 6641 29,7153 23 7631 13 8083 59 5629 13 6157 47 6647 17 7157 17 7633 17 8119 23 5633 43 6161 61 6649 61 7163 13 7657 13 8131 47 8567 13 9083 31 5671 53 6169 31 6667 59 7169 67 7661 47 8137 79 8579 23 9089 61 5681 13 6179 37 6683 41 7171 71 7663 79 8143 17 8587 31 9101 19 5699 41 6187 23 6697 37 7181 43 7697 43 8149 29 8593 13 9113 13 5707 13 6191 41 6707 19 7199 23 7709 13 8153 31 8611 79 9131 23 5713 29 6227 13 6731 53 7201 19 7729 59 8159 41 8621 37 9139 13 5723 59 6233 23 6739 23 7223 31 7739 71 8177 13 8633 89 9143 41 5729 17 6239 17 6749 17 7241 13 7747 61 8189 19 8639 53 9167 89 5759 13 6241 79 6751 43 7261 53 7751 23 8201 59 8651 41 9169 53 5767 73 6253 13 6757 29 7267 13 7769 17 8203 13 8653 17 9179 67 5771 29 6283 61 6767 67 7277 19 7771 19 8207 29 8671 13 9193 29 5773 23 6289 19 6773 13 7279 29 7781 31 8213 43 8683 19 9197 17 5777 53 6313 59 6799 13 7289 37 7783 43 8227 19 8711 31 921161 5809 37 6319 71 6817 17 7291 23 7787 13 8249 73 8717 23 9217 13 5833 19 6331 13 6821 19 7303 67 7801 29 8251 37 8749 13 9223 23 5837 13 6341 17 6847 41 7313 71 7807 37 8257 23 8759 19 9253 19 5891 43 6371 23 6851 13 7319 13 7811 73 8279 17 8773 31 9259 47 5893 71 6383 13 6859 19 7327 17 7813 13 8299 43 8777 67 9263 59 5899 17 6401 37 6877 13 7339 41 7831 41 8303 19 8791 59 9269 13 5909 19 6403 19 6887 71 7361 17,7837 17 8321 53 8797 19 9271 73 5911 23 6407 43 6889 83 7363 37 7849 47 8333 13 8801 13 9287 37 5917 61 6409 13 6893 61 7367 53 7859 29 8339 31 8809 23 9299 17 5921 31 6431 59 6901 67 7373 73 7871 17 8341 19 8843 37 9301 71 5933 17 6437 41 6913 31 7379 47 7891 13 8347 17 8851 53 9307 41 5941 13 6439 47 6929 13 7387 83 7897 53 8357 61 8857 17 9313 67 5947 19 6443 17 6931 29 7391 19 7913 41 8359 13 8873 19 9322 19 5959 59 6463 23 6943 53 7397 13,7921 89 8381 17 8879 13 9347 13 5963 67 6467 29 6953 17 7409 31 7939 17 8383 83 8881 83 9353 47 5969 47 6487 13 6973 19 7421 417943 13 8399 37 8891 17 9367 17 5977 43 6493 43 6989 29 7423 13 7957 73 8401 31 8903 29 9379 83 5983 3 6497 73 7003 47 7429 17 7961 19 8411 41 8909 59 9389 41 5989 53 6499 67 7009 43 7439 43 7967 31 8413 47 8917 37 9407 23 5993 3 6509 23 7031 79 7453 29 7969 13 8417 19 8927 79 9409 97 6001 17 6511 17 7033 13 7463 17 7979 79 8441 23 8947 23 9451 13 6019 13 6527 61 7037 31 7471 31 7981 23 8453 79 8957 13 9469 17 6023 19 6533 47 7061 23 7493 59 7991 61 8471 43 8959 17 9481 19 6031 37 6539 13 7067 37 7501 13 7999 19 8473 37 8977 47 9487 53 6049 23 6541 31 7081 73 7519 73 8003 53 8479 61 8983 13 9503 13 6059 73 6557 79 7087 19 7531 17 8021 13 8483 17 8989 89 9509 37 6071 13 6583 29 7093 41 7543 19 8023 71 8489 13 8993 17 9517 31 6077 59 6593 19 7097 47 7571 67 8027 23 8497 29 9017 71 9523 89 6103 17 6613 17 7099 31 7597 71 8033 29 8507 47 9019 29 9529 13 6107 31 6617 13 7111 13 7613 23 8047 13 8509 67 9047 83 9553 41 6109 41 6623 57 7123 17 7619 19 8051 83 8531 19 9061 13 No. Fac. 9557 19 9563 73 9571 17 9577 61 9589 43 9593 53 9599 29 9607 13 9617 59 9637 23 9641 31 9659 13 9671 19 9673 17 9683 23 9701 89 9703 31 9707 17 9727 71 9731 37 9761 43 9763 13 9773 29 9797 97 9799 41 9809 17 9827 31 9841 13 9847 43 9853 59 9869 71 9881 41 9893 13 9899 19 9913 23 9917 47 9937 19 9943 61 9953 37 9959 23 9971 13 9979 *7 9983 67 9991 97 9997 13 10001 73 |