CALCU-You need to refer to the sections on Congrue

You need to refer to the sections on Congruence and Arithmetic modulo n in Chapter 3 for this question. Consider numbers such as 19326 or 96123. One way to check whether they are divisible by 3 is to simply try to divide them directly. However, there is a test for divisibility by 3. Add up the digits, e.g. 1 + 9 + 3 + 2 + 6 = 21. Since the sum of the digits 21 is divisibly by 3, then both numbers are divisible by 3, since the sums of their digits are divisible by 3. A number such as 112 is not divisible by 3 since 1 + 1 + 2 = 4 is not divisible by 3. The goal of this question is to prove formally that this test for divisibility by 3 works for the general case. (a) Show that 10 ≡3 1 and 10k ≡3 1 for any positive integer k. (b) Show that A × 10k ≡3 A for any positive integers k and A. (c) Now consider a number where the digits are [ak, ak−1, · · · , a1, a0]. This number N is equivalent to N = ak × 10k + ak−1 × 10k−1 + · · · + a2 × 102 + a1 × 10 + a0, where ak is an integer from 1 to 9, and the rest of the ai are integers from 0 to 9. Show that N ≡3 ak + ak−1 + · · · + a2 + a1 + a0, and then show that N is divisible by 3 if and only if ak + ak−1 + · · · + a2 + a1 + a0 is divisible by 3. (d) Suggest a test for divisibility by 6.

Solution by Steps

step 1

To show that

10 \equiv_3 1

and

10^k \equiv_3 1

for any positive integer

k

, we start by noting that

10 \equiv 1 \pmod{3}

step 2

Since

10 \equiv 1 \pmod{3}

, raising both sides to the power of

k

gives

10^k \equiv 1^k \pmod{3}

step 3

Simplifying, we get

10^k \equiv 1 \pmod{3}

for any positive integer

k

step 4

To show that

A \times 10^k \equiv_3 A

for any positive integers

k

and

A

, we use the result from step 3

step 5

Since

10^k \equiv 1 \pmod{3}

, multiplying both sides by

A

gives

A \times 10^k \equiv A \times 1 \pmod{3}

step 6

Simplifying, we get

A \times 10^k \equiv A \pmod{3}

step 7

Consider a number

N

where the digits are

[a_k, a_{k-1}, \cdots, a_1, a_0]

. This number

N

is equivalent to

N = a_k \times 10^k + a_{k-1} \times 10^{k-1} + \cdots + a_2 \times 10^2 + a_1 \times 10 + a_0

step 8

Using the result from step 3, we know that

10^i \equiv 1 \pmod{3}

for any

i

step 9

Therefore,

N \equiv a_k \times 1 + a_{k-1} \times 1 + \cdots + a_2 \times 1 + a_1 \times 1 + a_0 \pmod{3}

step 10

Simplifying, we get

N \equiv a_k + a_{k-1} + \cdots + a_2 + a_1 + a_0 \pmod{3}

step 11

Thus,

N

is divisible by

3

if and only if

a_k + a_{k-1} + \cdots + a_2 + a_1 + a_0

is divisible by

3

step 12

To suggest a test for divisibility by

6

, note that a number is divisible by

6

if and only if it is divisible by both

2

and

3

step 13

Therefore, a number is divisible by

6

if it is even (last digit is

0, 2, 4, 6,

or

8

) and the sum of its digits is divisible by

3

Answer

A number is divisible by

3

if the sum of its digits is divisible by

3

. A number is divisible by

6

if it is even and the sum of its digits is divisible by

3

.

Key Concept

Divisibility rules for

3

and

6

Explanation

The sum of the digits of a number determines its divisibility by

3

. For divisibility by

6

, the number must be even and the sum of its digits must be divisible by

3

.

How can we prove that a number is divisible by 3 using the sum of its digits?

Solution by Steps

step 1

To prove that a number is divisible by 3 using the sum of its digits, we start by expressing the number in its decimal form. Let the number be

n

and its digits be

a_k, a_{k-1}, \ldots, a_1, a_0

. Then, we can write

n

as:

n = a_k \cdot 10^k + a_{k-1} \cdot 10^{k-1} + \cdots + a_1 \cdot 10 + a_0

step 2

Notice that

10 \equiv 1 \pmod{3}

. This means that any power of 10 is congruent to 1 modulo 3:

10^k \equiv 1^k \equiv 1 \pmod{3}

step 3

Using this property, we can simplify the expression for

n

modulo 3:

n \equiv a_k \cdot 1 + a_{k-1} \cdot 1 + \cdots + a_1 \cdot 1 + a_0 \cdot 1 \pmod{3}

n \equiv a_k + a_{k-1} + \cdots + a_1 + a_0 \pmod{3}

step 4

Therefore,

n

is divisible by 3 if and only if the sum of its digits

a_k + a_{k-1} + \cdots + a_1 + a_0

is divisible by 3

Answer

A number is divisible by 3 if the sum of its digits is divisible by 3.

Key Concept

Divisibility by 3 using the sum of digits

Explanation

A number is divisible by 3 if the sum of its digits is divisible by 3 because each power of 10 is congruent to 1 modulo 3.

Solution by Steps

step 1

Identify the highest order term in the function

f(n)

step 2

The highest order term in

f(n)

is

3n^2

step 3

According to Proposition 15, the theta notation is determined by the highest order term

step 4

Therefore,

f(n) = \Theta(n^2)

(b)

g(n) = (2n + 3)(4 + 5\ln n)

step 1

Expand the function

g(n)

step 2

g(n) = 2n \cdot 4 + 2n \cdot 5\ln n + 3 \cdot 4 + 3 \cdot 5\ln n = 8n + 10n\ln n + 12 + 15\ln n

step 3

Identify the highest order term in the expanded function

step 4

The highest order term is

10n\ln n

step 5

According to Proposition 15, the theta notation is determined by the highest order term

step 6

Therefore,

g(n) = \Theta(n\ln n)

(c)

h(n) = \frac{n^3 + 2n^2 + 5}{5n^2 + n + 1}

step 1

Identify the highest order terms in the numerator and the denominator

step 2

The highest order term in the numerator is

n^3

and in the denominator is

5n^2

step 3

Simplify the function by dividing the highest order terms

step 4

h(n) \approx \frac{n^3}{5n^2} = \frac{n}{5}

step 5

According to Proposition 16, the theta notation is determined by the simplified form

step 6

Therefore,

h(n) = \Theta(n)

Answer

(a)

\Theta(n^2)

, (b)

\Theta(n\ln n)

, (c)

\Theta(n)

Key Concept

Theta notation

Explanation

Theta notation describes the asymptotic behavior of functions, focusing on the highest order term to determine the growth rate.

Solution by Steps

step 1

Each roll of a die has 6 possible outcomes. Since the die is rolled 7 times, the total number of outcomes is

6^7

step 2

Calculate

6^7

:

6^7 = 279936

# (b) How many outcomes are there where 3 is not present?

step 1

If 3 is not present, each roll has 5 possible outcomes (1, 2, 4, 5, 6). Since the die is rolled 7 times, the total number of outcomes is

5^7

step 2

Calculate

5^7

:

5^7 = 78125

# (c) How many outcomes are there where 3 is present exactly once?

step 1

Choose 1 out of 7 rolls to be 3. This can be done in

\binom{7}{1}

ways

step 2

For the remaining 6 rolls, each has 5 possible outcomes. So, the number of outcomes is

5^6

step 3

Calculate

\binom{7}{1} \times 5^6

:

\binom{7}{1} = 7

and

5^6 = 15625

step 4

Multiply:

7 \times 15625 = 109375

# (d) How many outcomes are there where 3 is present at least twice?

step 1

Total outcomes minus outcomes where 3 is not present and outcomes where 3 is present exactly once

step 2

Calculate:

279936 - 78125 - 109375 = 92436

# (e) How many outcomes are there where 1 is present exactly once, 2 is present exactly twice, and 4 is present exactly four times?

step 1

The total number of rolls is 7. We need to arrange 1, 2, 2, 4, 4, 4, 4

step 2

The number of ways to arrange these is given by the multinomial coefficient:

\frac{7!}{1!2!4!}

step 3

Calculate:

\frac{7!}{1!2!4!} = \frac{5040}{1 \times 2 \times 24} = 105

Answer

(a) 279936

(b) 78125

(c) 109375

(d) 92436

(e) 105

Question 5 # (a) How many solutions are there if

x_{1}, x_{2}, x_{3} \geq 0

?

step 1

Use the stars and bars method to find the number of non-negative integer solutions to

x_{1} + x_{2} + x_{3} = 15

step 2

The formula is

\binom{n+k-1}{k-1}

where

n=15

and

k=3

step 3

Calculate:

\binom{15+3-1}{3-1} = \binom{17}{2} = 136

# (b) How many solutions are there if

x_{1}, x_{2}, x_{3} \geq 1

?

step 1

Substitute

x_{1} = y_{1} + 1

,

x_{2} = y_{2} + 1

,

x_{3} = y_{3} + 1

where

y_{1}, y_{2}, y_{3} \geq 0

step 2

The equation becomes

y_{1} + y_{2} + y_{3} = 12

step 3

Use the stars and bars method:

\binom{12+3-1}{3-1} = \binom{14}{2} = 91

# (c) How many solutions are there if

1 \leq x_{1} \leq 3

,

x_{2} \geq 0

,

x_{3} \geq 0

?

step 1

Consider the cases for

x_{1}

:

x_{1} = 1

,

x_{1} = 2

, and

x_{1} = 3

step 2

For

x_{1} = 1

:

x_{2} + x_{3} = 14

, solutions are

\binom{14+2-1}{2-1} = \binom{15}{1} = 15

step 3

For

x_{1} = 2

:

x_{2} + x_{3} = 13

, solutions are

\binom{13+2-1}{2-1} = \binom{14}{1} = 14

step 4

For

x_{1} = 3

:

x_{2} + x_{3} = 12

, solutions are

\binom{12+2-1}{2-1} = \binom{13}{1} = 13

step 5

Sum the solutions:

15 + 14 + 13 = 42

Answer

(a) 136

(b) 91

(c) 42

Question 6 # (a) Suppose

x_{k}=m^{k}

is a general solution, set up a quadratic equation for

m

.

step 1

Substitute

x_{k} = m^k

into the recurrence relation

x_{k} = p x_{k+1} + q x_{k-1}

step 2

This gives

m^k = p m^{k+1} + q m^{k-1}

step 3

Divide by

m^{k-1}

:

m^2 = p m + q

step 4

Rearrange to form the quadratic equation:

m^2 - p m - q = 0

# (b) If

p \neq q

, let

c=\frac{q}{p}

, solve for the roots of

m

in part (a) and use the conditions

x_{0}=0

and

x_{N}=1

to find the solution to

x_{k}

.

step 1

Solve the quadratic equation

m^2 - p m - q = 0

using the quadratic formula:

m = \frac{p \pm \sqrt{p^2 + 4q}}{2}

step 2

Let the roots be

m_1

and

m_2

step 3

The general solution is

x_k = A m_1^k + B m_2^k

step 4

Use the boundary conditions

x_0 = 0

and

x_N = 1

to find

A

and

B

step 5

x_0 = 0 \Rightarrow A + B = 0 \Rightarrow B = -A

step 6

x_N = 1 \Rightarrow A m_1^N - A m_2^N = 1 \Rightarrow A (m_1^N - m_2^N) = 1 \Rightarrow A = \frac{1}{m_1^N - m_2^N}

step 7

Substitute

A

and

B

back into the general solution:

x_k = \frac{m_1^k - m_2^k}{m_1^N - m_2^N}

# (c) If

p=q=\frac{1}{2}

, solve for the roots of

m

in part (a) and use the conditions

x_{0}=0

and

x_{N}=1

to find the solution to

x_{k}

.

step 1

Substitute

p = q = \frac{1}{2}

into the quadratic equation:

m^2 - \frac{1}{2} m - \frac{1}{2} = 0

step 2

Solve the quadratic equation:

m = \frac{\frac{1}{2} \pm \sqrt{\left(\frac{1}{2}\right)^2 + 2 \cdot \frac{1}{2}}}{2} = \frac{\frac{1}{2} \pm \sqrt{\frac{1}{4} + 1}}{2} = \frac{\frac{1}{2} \pm \sqrt{\frac{5}{4}}}{2} = \frac{\frac{1}{2} \pm \frac{\sqrt{5}}{2}}{2} = \frac{1 \pm \sqrt{5}}{4}

step 3

The roots are

m_1 = \frac{1 + \sqrt{5}}{4}

and

m_2 = \frac{1 - \sqrt{5}}{4}

step 4

The general solution is

x_k = A m_1^k + B m_2^k

step 5

Use the boundary conditions

x_0 = 0

and

x_N = 1

to find

A

and

B

step 6

x_0 = 0 \Rightarrow A + B = 0 \Rightarrow B = -A

step 7

x_N = 1 \Rightarrow A m_1^N - A m_2^N = 1 \Rightarrow A (m_1^N - m_2^N) = 1 \Rightarrow A = \frac{1}{m_1^N - m_2^N}

step 8

Substitute

A

and

B

back into the general solution:

x_k = \frac{m_1^k - m_2^k}{m_1^N - m_2^N}

Answer

(a)

m^2 - p m - q = 0

(b)

x_k = \frac{m_1^k - m_2^k}{m_1^N - m_2^N}

(c)

x_k = \frac{m_1^k - m_2^k}{m_1^N - m_2^N}

Key Concept

Probability and combinatorics in rolling dice and solving integer equations

Explanation

The solutions involve calculating the total number of outcomes using combinatorial methods and solving recurrence relations using boundary conditions.

Generated Graph

Solution by Steps

step 1

We start with the given equation:

300000 \cdot (1 + \frac{0.04}{12})^{120} - b \cdot \frac{(1 + \frac{0.04}{12})^{120} - 1}{\frac{0.04}{12}} = 0

step 2

Simplify the monthly interest rate:

\frac{0.04}{12} = 0.0033333

step 3

Substitute the monthly interest rate into the equation:

300000 \cdot (1 + 0.0033333)^{120} - b \cdot \frac{(1 + 0.0033333)^{120} - 1}{0.0033333} = 0

step 4

Calculate

(1 + 0.0033333)^{120}

:

(1 + 0.0033333)^{120} \approx 1.488863

step 5

Substitute the calculated value into the equation:

300000 \cdot 1.488863 - b \cdot \frac{1.488863 - 1}{0.0033333} = 0

step 6

Simplify the equation:

300000 \cdot 1.488863 - b \cdot 146.6589 = 0

step 7

Solve for

b

:

b = \frac{300000 \cdot 1.488863}{146.6589} \approx 3037.35

Answer

b \approx 3037.35

Key Concept

Loan repayment calculation

Explanation

The monthly payment

b

is determined by solving the equation that balances the loan amount with the interest and payments over the loan period.

Solution by Steps

step 1

To find the number of ways to arrange 6 stones in a circular pattern with a discernable front and back, we use the formula for circular permutations:

(n-1)!

step 2

Here,

n = 6

, so the number of arrangements is

(6-1)! = 5!

step 3

Calculate

5!

:

5! = 5 \times 4 \times 3 \times 2 \times 1 = 120

Answer

120

Part (b)

step 1

To find the number of ways to arrange 6 stones in a circular pattern without a discernable front and back, we use the formula for circular permutations with reflection:

\frac{(n-1)!}{2}

step 2

Here,

n = 6

, so the number of arrangements is

\frac{(6-1)!}{2} = \frac{5!}{2}

step 3

Calculate

\frac{5!}{2}

:

\frac{5!}{2} = \frac{120}{2} = 60

Answer

60

Key Concept

Circular Permutations

Explanation

The number of ways to arrange objects in a circle differs based on whether the arrangement has a discernable front and back. For a circle with a discernable front and back, the formula is

(n-1)!

. For a circle without a discernable front and back, the formula is

\frac{(n-1)!}{2}

.

AskSia

Plus