Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2017 AMC 12B Problems/Problem 19: Difference between revisions

← Older edit
Mendenhallisbald (talk | contribs)
editor
71 edits
 
(28 intermediate revisions by 7 users not shown)
Line 4: Line 4:
<math>\textbf{(A)}\ 1\qquad\textbf{(B)}\ 4\qquad\textbf{(C)}\ 9\qquad\textbf{(D)}\ 18\qquad\textbf{(E)}\ 44</math>
<math>\textbf{(A)}\ 1\qquad\textbf{(B)}\ 4\qquad\textbf{(C)}\ 9\qquad\textbf{(D)}\ 18\qquad\textbf{(E)}\ 44</math>


==Solution==
==Solution 1==


We will consider this number <math>\bmod\ 5</math> and <math>\bmod\ 9</math>. By looking at the last digit, it is obvious that the number is <math>\equiv 4\bmod\ 5</math>. To calculate the number <math>\bmod\ 9</math>, note that
We will consider this number <math>\bmod\ 5</math> and <math>\bmod\ 9</math>. By looking at the last digit, it is obvious that the number is <math>\equiv 4\bmod\ 5</math>. To calculate the number <math>\bmod\ 9</math>, note that
Line 14: Line 14:
<cmath>\frac{44\cdot 45}{2} = 22\cdot 45 \equiv 0\bmod\ 9.</cmath>
<cmath>\frac{44\cdot 45}{2} = 22\cdot 45 \equiv 0\bmod\ 9.</cmath>


Let <math>x</math> be the remainder when this number is divided by <math>45</math>. We know that <math>x\equiv 0 \pmod {9}</math> and <math>x\equiv 4 \pmod {5}</math>, so by the Chinese remainder theorem, since <math>9(-1)\equiv 1 \pmod{5}</math>, <math>x\equiv 5(0)+9(-1)(4) \pmod {5\cdot 9}</math>, or <math>x\equiv -36 \equiv 9 \pmod {45}</math>. So the answer is <math>\boxed {\bold {(C)}}</math>.
Let <math>x</math> be the remainder when this number is divided by <math>45</math>. We know that <math>x\equiv 0 \pmod {9}</math> and <math>x\equiv 4 \pmod {5}</math>, so by the Chinese remainder theorem, since <math>9(-1)\equiv 1 \pmod{5}</math>, <math>x\equiv 5(0)+9(-1)(4) \pmod {5\cdot 9}</math>, or <math>x\equiv -36 \equiv 9 \pmod {45}</math>. So the answer is <math>\boxed {\textbf {(C)}}</math>.


==Solution 2==
==Solution 2==


We know that this number is divisible by 9 because the sum of the digits is (22*45) which is divisible by 9. Subtracting 9 from the integer we get 1234 ... 4335, which is also divisible by 5,making it also divisible by 45. Thus the remainder is 9.
We know that this number is divisible by <math>9</math> because the sum of the digits is <math>270</math>, which is divisible by <math>9</math>. If we subtracted <math>9</math> from the integer we would get <math>1234 \cdots 4335</math>, which is also divisible by <math>5</math> and by <math>45</math>. Thus the remainder is <math>9</math>, or <math>\boxed{\textbf{C}}</math>.
 
==Solution 3 (Beginner's Method)==
 
To find the sum of digits of our number, we break it up into <math>5</math> cases, starting with <math>0</math>, <math>1</math>, <math>2</math>, <math>3</math>, or <math>4</math>.
 
Case 1: <math>1+2+3+\cdots+9 = 45</math>,
 
Case 2: <math>1+0+1+1+1+2+\cdots+1+8+1+9 = 55</math> (We add 10 to the previous cases, as we are in the next ten's place)
 
Case 3: <math>2+0+2+1+\cdots+2+9 = 65</math>,
 
Case 4: <math>3+0+3+1+\cdots+3+9 = 75</math>,
 
Case 5: <math>4+0+4+1+\cdots+4+4 = 30</math>,
 
Thus the sum of the digits is <math>45+55+65+75+30 = 270</math>, so the number is divisible by <math>9</math>. We notice that the number ends in "<math>4</math>", which is <math>9</math> more than a multiple of <math>5</math>. Thus if we subtracted <math>9</math> from our number it would be divisible by <math>5</math>, and <math>5\cdot 9 = 45</math>. (Multiple of n - n = Multiple of n)
 
 
So our remainder is <math>\boxed{\textbf{(C)}\,9}</math>, the value we need to add to the multiple of <math>45</math> to get to our number.
 
==Solution 4==
 
We notice that <math>10^{k}\equiv 10 \pmod {45}</math>.
 
Hence <math>N = 44+43\cdot10^{2}+42\cdot10^{4}+\cdots+10^{78} \equiv 44+10\cdot(1+2+3+\cdots+43)\equiv 9 \pmod {45}.</math>
 
Choose <math>\boxed{\textbf{(C)}\,9}</math>
 
~ PythZhou
 
==Solution 5 (Solution 2 but more in-depth)==
 
The sum of all of the digits is just the sum of consecutive numbers from <math>1 -> 44</math> or <math>\frac{44}{2}(45) = 990</math>. The prime factorization of <math>45</math> is <math>3^2 * 5</math>. So if a number is divisible by <math>45</math> it has to both be divisible by <math>9</math> and <math>5</math>. The first number that satisfies this ends in <math>35</math> because the ten's digit is one greater than the ten's digit in the consecutive numbers from <math>1</math> to <math>44</math>, and the one's digit is one less than this number, and the number ends in a 5. The difference between <math>35</math> and <math>44</math> is <math>9</math> giving <math>\boxed{\textbf{(C)}\,9}</math>.
 
~PeterDoesPhysics
 
== Video Solution by OmegaLearn==
https://youtu.be/zfChnbMGLVQ?t=3342
 
~ pi_is_3.14


==See Also==
==See Also==

Latest revision as of 16:06, 2 September 2024

Problem

Let $N=123456789101112\dots4344$ be the $79$-digit number that is formed by writing the integers from $1$ to $44$ in order, one after the other. What is the remainder when $N$ is divided by $45$?

$\textbf{(A)}\ 1\qquad\textbf{(B)}\ 4\qquad\textbf{(C)}\ 9\qquad\textbf{(D)}\ 18\qquad\textbf{(E)}\ 44$

Solution 1

We will consider this number $\bmod\ 5$ and $\bmod\ 9$. By looking at the last digit, it is obvious that the number is $\equiv 4\bmod\ 5$. To calculate the number $\bmod\ 9$, note that

\[123456\cdots 4344 \equiv 1+2+3+4+5+6+7+8+9+(1+0)+(1+1)+\cdots+(4+3)+(4+4) \equiv 1+2+\cdots+44 \bmod\ 9,\]

so it is equivalent to

\[\frac{44\cdot 45}{2} = 22\cdot 45 \equiv 0\bmod\ 9.\]

Let $x$ be the remainder when this number is divided by $45$. We know that $x\equiv 0 \pmod {9}$ and $x\equiv 4 \pmod {5}$, so by the Chinese remainder theorem, since $9(-1)\equiv 1 \pmod{5}$, $x\equiv 5(0)+9(-1)(4) \pmod {5\cdot 9}$, or $x\equiv -36 \equiv 9 \pmod {45}$. So the answer is $\boxed {\textbf {(C)}}$.

Solution 2

We know that this number is divisible by $9$ because the sum of the digits is $270$, which is divisible by $9$. If we subtracted $9$ from the integer we would get $1234 \cdots 4335$, which is also divisible by $5$ and by $45$. Thus the remainder is $9$, or $\boxed{\textbf{C}}$.

Solution 3 (Beginner's Method)

To find the sum of digits of our number, we break it up into $5$ cases, starting with $0$, $1$, $2$, $3$, or $4$.

Case 1: $1+2+3+\cdots+9 = 45$,

Case 2: $1+0+1+1+1+2+\cdots+1+8+1+9 = 55$ (We add 10 to the previous cases, as we are in the next ten's place)

Case 3: $2+0+2+1+\cdots+2+9 = 65$,

Case 4: $3+0+3+1+\cdots+3+9 = 75$,

Case 5: $4+0+4+1+\cdots+4+4 = 30$,

Thus the sum of the digits is $45+55+65+75+30 = 270$, so the number is divisible by $9$. We notice that the number ends in "$4$", which is $9$ more than a multiple of $5$. Thus if we subtracted $9$ from our number it would be divisible by $5$, and $5\cdot 9 = 45$. (Multiple of n - n = Multiple of n)


So our remainder is $\boxed{\textbf{(C)}\,9}$, the value we need to add to the multiple of $45$ to get to our number.

Solution 4

We notice that $10^{k}\equiv 10 \pmod {45}$.

Hence $N = 44+43\cdot10^{2}+42\cdot10^{4}+\cdots+10^{78} \equiv 44+10\cdot(1+2+3+\cdots+43)\equiv 9 \pmod {45}.$

Choose $\boxed{\textbf{(C)}\,9}$

~ PythZhou

Solution 5 (Solution 2 but more in-depth)

The sum of all of the digits is just the sum of consecutive numbers from $1 -> 44$ or $\frac{44}{2}(45) = 990$. The prime factorization of $45$ is $3^2 * 5$. So if a number is divisible by $45$ it has to both be divisible by $9$ and $5$. The first number that satisfies this ends in $35$ because the ten's digit is one greater than the ten's digit in the consecutive numbers from $1$ to $44$, and the one's digit is one less than this number, and the number ends in a 5. The difference between $35$ and $44$ is $9$ giving $\boxed{\textbf{(C)}\,9}$.

~PeterDoesPhysics

Video Solution by OmegaLearn

https://youtu.be/zfChnbMGLVQ?t=3342

~ pi_is_3.14

See Also

2017 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 18 		Followed by
Problem 20
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions
2017 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 22 		Followed by
Problem 24
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

These problems are copyrighted © by the Mathematical Association of America.

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=2017_AMC_12B_Problems/Problem_19&oldid=226237"