Lesson Introductory problems on divisibility of integer numbers
Algebra
->
Divisibility and Prime Numbers
->
Lessons
-> Lesson Introductory problems on divisibility of integer numbers
Log On
Algebra: Divisibility and Prime Numbers
Section
Solvers
Solvers
Lessons
Lessons
Answers archive
Answers
Source code of 'Introductory problems on divisibility of integer numbers'
This Lesson (Introductory problems on divisibility of integer numbers)
was created by by
ikleyn(52908)
:
View Source
,
Show
About ikleyn
:
<H2>Introductory problems on divisibility of integer numbers</H2> <H3>Problem 1</H3>For any integer n, prove that 3 divides one of the integers n, n + 1 or 2n + 1. <B>Solution</B> <pre> a) If n divides 3 then the statement is proved. If n does not divide 3 without a remainder, then the remainder is either 1 or 2. b) If the remainder is 1, then 2n+1 has the remainder 2*1+1 = 3; in other words, then 2n +1 is a multiple of 3. c) If the remainder is 2, then n+1 is divisible by 3. Thus, in all cases one of the three numbers n, n+1 or 2n+1 is divisible by 3. </pre> QED. Proved and solved. <H3>Problem 2</H3>For any integer n, prove that 3 divides one of n, n + 2 or n + 4. <B>Solution</B> <pre> a) If n divides 3 then the statement is proved. If n does not divide 3 without a remainder, then the remainder is either 1 or 2. b) If the remainder is 1, then n+2 is divisible by 3. c) If the remainder is 2, then n+4 is divisible by 3. Thus, in all cases one of the three numbers n, n+2 or n+4 is divisible by 3. </pre> QED. Proved and solved. <H3>Problem 3</H3>For any integer n, prove that 3 divides one of n, 2n - 1 or 2n +1. <B>Solution</B> <H3>Problem 4</H3>Show that if n is an odd integer, then {{{n^3-n}}} is a multiple of 24. <B>Solution</B> <pre> {{{n^3 - n}}} = {{{n*(n^2-1)}}} = {{{n*(n-1)*(n+1)}}} = {{{(n-1)*n*(n+1)}}}. You have a product of three consecutive integers. One of them is a multiple of 3. If n is odd, then both (n-1) and (n+1) are even, i.e. are multiples of 2. Moreover, one of these two is a multiple of 4. Therefore, the entire product is a multiple of 2*3*4 = 24. </pre> QED. Proved and solved. <H3>Problem 5</H3>Prove that for any integer n, 5 divides {{{n^5-n}}}. <B>Solution</B> <pre> {{{n^5 - n}}} = {{{n*(n^4-1)}}} = {{{n*(n^2-1)*(n^2+1)}}} = {{{n*(n-1)*(n+1)*(n^2+1)}}} = {{{(n-1)*n*(n+1)*(n^2+1)}}}. If n is a multiple of 5, the statement is true. If n gives the remainder 1 when divided by 5, then the factor (n-1) is a multiple of 5, and the statement is true. If n gives the remainder 4 when divided by 5, then the factor (n+1) is a multiple of 5, and the statement is true. If n gives the remainder 2 when divided by 5, then the factor (n^2+1) is a multiple of 5. Indeed, the remainder of division by 5 is {{{2^2+1}}} = 5 (equivalent to 0) in this case, and the statement is true. If n gives the remainder 3 when divided by 5, then the factor (n^2+1) is a multiple of 5. Indeed, the remainder of division by 5 is {{{3^2+1}}} = 10 (equivalent to 0) in this case, and the statement is true. Thus the statement is true in all cases. </pre> QED. Proved and solved. <H3>Problem 6</H3>Prove that {{{n^8 - n^4}}} is divisible by 5 for any natural n. <B>Solution</B> <pre> Let us factor {{{n^8 - n^4}}} as far as we can: {{{n^8 - n^4}}} = {{{n^4*(n^4-1)}}} = {{{n^4*(n^2+1)*(n^2-1)}}} = {{{n^4*(n^2+1)*(n+1)*(n-1)}}} Now, if n is a multiple of 5, then {{{n^8 - n^4}}} is a multiple of 5. If n gives a remainder 1 when divided by 5, then the factor (n-1) is a multiple of 5. If n gives a remainder 4 when divided by 5, then the factor (n+1) is a multiple of 5. If n gives a remainder 2 or 3 when divided by 5, then the factor {{{(n^2+1)}}} is a multiple of 5. So, in any case {{{n^8 - n^4}}} is a multiple of 5, and the statement is proved. </pre> QED. Proved and solved. <H3>Problem 7</H3>How many positive integers " n " are there such that 2n+1 is a divisor of 8n+46 ? <B>Solution</B> <pre> Let's assume that (2n+1) is a divisor of N = 8n+46. Notice that that (2n+1) is a divisor of the number M = 8n+4 (simply because 8n+4 = 4*(2n+1) ). It implies that the difference N-M is a multiple of (2n+1), too. But the difference N-M is equal to (8n+46) - (8n+4) = 46-4 = 42. Thus the number (2n+1) is a divisor of the number 42. We can list all the ODD divisors of the number 42. They are 3, 7 and 21, giving these equations to determine n 2n+1 = 3; 2n+1 = 7 and 2n+1 = 21. These equations have the following solutions, respectively n = 1; n = 3 and n = 10. So, we solved the problem and found out all opportunities for n as 1, 3 and 10. <U>ANSWER</U> </pre> <H3>Problem 8</H3>A six-digit number is formed by repeating a three-digit number as in 639639. Find the sum of the prime factors all such numbers have in common. <B>Solution</B> <pre> All these six-digit numbers, described in the post, are of the form N = 1000n + n = 1001n, where n is a/(any) three digit number. Therefore, all such 6-digit numbers have common factor 1001, and this number 1001 is their Greatest Common Divisor. The prime decomposition of number 1001 is 1001 = 7*11*13. Its positive prime factors are 7, 11, 13. The sum of these factors is 7 + 11 + 13 = 31. <U>ANSWER</U>. 31. </pre> My other lessons in this site on miscellaneous problems on divisibility of integer numbers are - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Light-flashes-on-a-Christmas-tree-and--a-Least-Common-Multiple.lesson>Light flashes on a Christmas tree and a Least Common Multiple</A> - <A HREF=http://www.algebra.com/algebra/homework/divisibility/lessons/The-number-that-leaves-a-remainder-1-when-divided-by-2-by-3-by-4-by-5-and-so-on-until-9.lesson>The number that leaves a remainder 1 when divided by 2, by 3, by 4, by 5 and so on until 9</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/The-number-rem4-mod7-rem5-mod8-and-rem6-mod9.lesson>The number which gives remainder 4 when divided by 7, remainder 5 when divided by 8 and remainder 6 when divided by 9</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Finding-Greatest-Common-Divisor-of-integer-numbers.lesson>Finding Greatest Common Divisor of integer numbers</A> - <A HREF=http://www.algebra.com/algebra/homework/divisibility/lessons/Relativity-prime-numbers-help-to-solve-the-problem.lesson>Relatively prime numbers help to solve problems</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Solving-equations-in-integer-numbers.lesson>Solving equations in integer numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Quadratic-polynomial-with-odd-integer-coefs-can-not-have-a-rational-root.lesson>Quadratic polynomial with odd integer coefficients can not have a rational root</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/Proving-the-equation-has-no-integer-solutions.lesson>Proving an equation has no integer solutions</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Composite-number-of-the-form-%284n%2B3%29-must--have-a-prime-divisor-of-the-form-%284n%2B3%29.lesson>Composite number of the form (4n+3) must have a prime divisor of the form (4n+3)</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Problems-on-divisors-of-a-given-number.lesson>Problems on divisors of a given number</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/How-many-three-digit-numbers-are-multiples-of-both-5-and-7.lesson>How many three-digit numbers are multiples of both 5 and 7?</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/How-many-3-digit-numbers-are-not-dvsbl-by-2-not-dvsbl-by-3-notdvsbl-by-either-2-or-3.lesson>How many 3-digit numbers are not divisible by 2; not divisible by 3; not divisible by either 2 or 3</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/How-many-integer-numbers-in-the-range-1-300-are-divisible-by.lesson>How many integer numbers in the range 1-300 are divisible by at least one of the integers 4, 6 and 15 ?</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Find-the-remainder-of-division.lesson>Find the remainder of division </A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Why-3%5En%2B7%5En-2-is-divisible-by-8-for-all-positive-integer-n.lesson>Why 3^n + 7^n - 2 is divisible by 8 for all positive integer n ?</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/What-is--the-last-digit-of-the-number-a%5En.lesson>What is the last digit of the number a^n ?</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Find-the-last-three-digits-of-these-numbers.lesson>Find the last three digits of these numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Find-the-two-last-digits-of-the-number-3%5E123%2B7%5E123%2B9%5E123.lesson>Find the last two digits of the number 3^123 + 7^123 + 9^123</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/Find-the-last-two-digits-of-%281%21-%2B-2%21-%2B-3%21-%2B-%2B-2024%21%29%5E2024.lesson>Find the last two digits of (1! + 2! + 3! + ... + 2024!)^2024</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Find-n-th-term-of-a-sequence.lesson>Find n-th term of a sequence</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Solving-one-Diofantine-equation.lesson>Solving Diophantine equations</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Determine-the-number-of-integer-solutions-to-equation-n%5E2%2B18n%2B3=m%5E2.lesson>How many integers of the form n^2 + 18n + 13 are perfect squares</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Miscellaneous-problems-on-divisibility-numbers.lesson>Miscellaneous problems on divisibility numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Find-the-sum-of-digits-of-integer-numbers.lesson>Find the sum of digits of integer numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Two-digit-numbers-with-digit-9.lesson>Two-digit numbers with digit "9"</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Find-a-triangle-with-integer-side-lengths-and-integer-area.lesson>Find a triangle with integer side lengths and integer area</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Math-circle-level-problem-on-the-hundred-handed-monster-Briareus.lesson>Math circle level problem on the hundred-handed monster Briareus</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Math-Citcle-level-problem-on-lockers-and-divisors.lesson>Math Circle level problem on lockers and divisors of integer numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Nice-entertaiment-problem-What-numbers-John-is-thinking-about.lesson>Nice entertainment problems related to divisibility property</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Solving-problems-on-modular-arithmetic.lesson>Solving problems on modular arithmetic</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Using-the-little-Fermat-theorem-to-solve-a-problem-on-modular-arithmetic.lesson#google_vignette>Using the little Fermat's theorem to solve a problem on modular arithmetic</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/OVERVIEW-of-miscellanious-solved-problems-on-divisibility-of-numbers.lesson>OVERVIEW of miscellaneous solved problems on divisibility of integer numbers</A>
