Lesson Find the remainder of division
Algebra
->
Divisibility and Prime Numbers
-> Lesson Find the remainder of division
Log On
Algebra: Divisibility and Prime Numbers
Section
Solvers
Solvers
Lessons
Lessons
Answers archive
Answers
Source code of 'Find the remainder of division'
This Lesson (Find the remainder of division)
was created by by
ikleyn(52803)
:
View Source
,
Show
About ikleyn
:
<H2>Find the remainder of division</H2> <H3>Problem 1</H3>Find the remainder modulo 36 of {{{44427^3456789}}}. <B>Solution</B> <pre> Notice that the remainder of the number 44427 divided by 36 is 3: 44427 = 36*1234 + 3. In other words, 44427 == 3 (mod 36). Therefore, 44427 modulo 36 is 3, and any degree {{{44427^n}}} modulo 36 is equal to the same degree of 3 modulo 36. Now, {{{3^2}}} == 9 mod 36 {{{3^3}}} == {{{3*9}}} mod 36 == 27 mod 36 {{{3^4}}} == {{{3*(3^3)}}} mod 36 == 3*27 mod 36 == 81 mod 36 == 9 mod 36. {{{3^5}}} == {{{3*(3^4)}}} mod 36 == 3*9 mod 36 == 27 mod 36. {{{3^6}}} == {{{3*(3^5)}}} mod 36 == 3*27 mod 36 == 81 mod 36 == 9 mod 36. You see that the degrees {{{3^n}}} modulo 36 form a cyclic sequence n 1 2 3 4 5 6 7 8 9 {{{3^n}}} mod 36 3 9 27 9 27 9 27 9 27 Thus for n > 1, {{{3^n}}} mod 36 is 9 for <U>EVEN VALUES of n</U> and is 27 for <U>ODD VALUES of n</U>. </pre> <H3>Problem 2</H3>What remainder is left when the number {{{567288133^6}}} is divided by 8? <B>Solution</B> <pre> It is easy to check directly that 567288133 gives the remainder 5 when divided by 8. By the way, for it, only three last digits of a number are important. We write 567288133 == 5 mod 8. It means that {{{567288133^6}}} gives the remainder {{{5^6}}} when divided by 8. Next, {{{5^6}}} = 15625. It is also easy to check directly that the remainder {15625 mod 8} is the same as {1 mod 8}. (and again, for it, only three last digits of the number 15625 do matter). <U>ANSWER</U>. When the number {{{(567288133)^6}}} is divided by 8, the remainder is 1. </pre> <H3>Problem 3</H3>What remainder is left when the number {{{274563358^5}}} is divided by 9? <B>Solution</B> Use the rule of divisibility by 9: <pre> The remainder of divisibility by 9 of the number N is the same, as the remainder of the sum of digits of the number N when divided by 9. </pre> <pre> The number 274563358 has the sum of its digits 2+7+4+5+6+3+3+5+8 = 43. So, the number 274563358 itself, when divided by 9, gives the same remainder as the sum of its digits 43 divided by 9, i.e. 43 mod 9 = 7. Hence, {{{274563358^5}}} when divided by 9 gives the same remainder as the number {{{7^5}}} = 16807 when divided by 9. Again, the number 16807 has the sum of the digits 1+6+8+7 = 22. Therefore, the answer to the problem's question is 22 mod 9 = 4. </pre> <H3>Problem 4</H3>Find the remainder when {{{40^13}}} is divided by 81. <B>Solution</B> It is clear that the mathematical meaning of this problem is not to follow literally the written formula. Its meaning is to decrease the degrees and values of participating numbers to make calculations easier using standard properties of operations of modular arithmetic. <pre> Following this idea, I write 40 = 36 + 4, {{{40^13}}} = {{{(36+4)^13}}}. Next we should apply the Newtonian binomial formula. It will give the sum of the terms {{{C[13]^k*36^k*4^(13-k)}}}, k = 0, 1, 2, 3, . . . , 13. All the terms with k >= 2 will be zero by modulo 81, since 36 = 9*4. Therefore, we can exclude all these terms from our consideration. So, the terms under our consideration are the terms with k= 0 and k= 1, or {{{C[13]^0*4^13}}} + {{{C[13]^1*36*4^12}}} = {{{4^13}}} + {{{13*36*4^12}}}. This expression is easy to calculate using a regular calculator or Excel spreadsheet; its value is 7918845952. Finally, 7918845952 mod 81 is 22 (use long division or Excel function mod) So, the <U>ANSWER</U> is 22. </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/Introductory-problems-on-divisibility-numbers.lesson>Introductory problems on divisibility of integer numbers</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 the problem</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/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>
