AAM-HW-2

Problem 1.

The aspect ratio of a rectangular image or screen is the ratio of its width to its height. It is usually expressed as , assuming .

  1. Calculate the aspect ratio of your phone or computer, simplify so that x : y are integers in lowest terms,
    i.e. gcd(x, y) = 1.

    • What is the aspect ratio of TV series, anime, or video channels (Bilibili, YouTube...) that you are currently watching?
      Phone/computer aspect ratio: Example - → , so 16:9.

    • Name one TV series and one anime with a 4:3 aspect ratio, together with its release date.
      TV series with 4:3 aspect ratio: Friends (Released: September 22, 1994).
      Anime with 4:3 aspect ratio: Naruto (Season 1) (Released: October 3, 2002).

  2. What is the aspect ratio of a rectangle that when folded in half lengthwise yields a smaller rectangle with the same aspect ratio?

    • Where does this aspect ratio appear in everyday life?
      1). The aspect ratio is (used for A-series paper sizes like A4, A3).
      2). Seen in paper folding, as A-series papers retain shape when halved.

Problem 2. Homogeneous Linear Recurrence with constant coefficients

A sequence of numbers defined by specifying the values of and recursively defining
where are given constants. Someone got lazy and guessed that each term might look like for some magical common ratio .

i. Write down an equation for , and find all solutions for in terms of and .

i. Equation for and its solutions:

Given the recurrence relation:
we guess . Substituting into the recurrence:

Dividing through by (for ):

Rearranging:

This is a quadratic equation:

Thus, the two solutions for in terms of and are:

ii. In the case of Fibonacci numbers , what are the two solutions, ?

ii. Fibonacci numbers :

For Fibonacci numbers:
we have and . Substituting into the quadratic equation:

Solving using the quadratic formula:

Thus, the two solutions are:

iii. It is not true that or . Someone now guesses that a linear combination might work:

where and are some magical coefficients that correctly mix the two solutions.
Knowing that , solve for and .

Solution to part iii:

The guess is that:
where and are the roots of the recurrence relation (), i.e., (the golden ratio) and .

We are tasked with finding and using the initial conditions and .

Step 1: Use the first condition
Substituting :

Since :

From , we get:
Thus:

Step 2: Use the second condition

Substituting :

Since , substitute into the equation:

Factor :

From , we get:

Step 3: Compute
Recall that and . So:

Simplify:

Thus:

Solve for :

From , we get:

Final Answer:

Problem 3. Combinatorics. Solve one of the following two questions.

Choose the first question

i. Mr. Chou is a nunchucks ("dual-section stick") master. He shouts either in "Heng!" (1 beat) or "Ha-Hi!" (2 beats).

For example, for 4 beats, he can shout "Heng Heng Ha-Hi!".

  • In how many possible ways can Mr. Chou shout for a combo move with 13 beats?

Ancient Indian poet and mathematician Pingala (around 200 BC) studied questions of this type, in the context of Sanskrit poetry.

To solve how many ways Mr. Chou can shout for 13 beats:

  • Each beat combo can consist of:
    • "Heng!" (1 beat),
    • "Ha-Hi!" (2 beats).

The problem reduces to a Fibonacci sequence:
with base cases:

Compute up to :

Final Answer: .

Problem 4: Prime Factorization and Euler's Totient Function

  1. What is the prime factorization of 60?

    Prime factorization:

  2. List all numbers between 1 and 60 which are coprime to 60. What is Euler's totient ?

    • A number is coprime to 60 if it shares no common prime factors with .
      That means numbers that are not divisible by the prime factors .

    • The numbers coprime to 60 are:
      .

    • Euler's totient function for :
      Simplifying:

  3. For two of the numbers coprime with 60 (except 1), write down another number so that .
    Let's find the modular inverses for two numbers:

    • Consider . Solve .
      Using the extended Euclidean algorithm, we find . So:

    • Consider . Solve .
      Using the extended Euclidean algorithm, we find . So:

Problem 5.

i. Use the Euclidean Algorithm to show that 314 and 159 are coprime.

  • Apply the Euclidean algorithm to :
    The gcd is , which means and are coprime.

ii. Use the Euclidean Algorithm to find .

  1. Apply the Euclidean algorithm to :
    The gcd is .

  2. Decompose a rectangle into squares of various sizes.

Sq1Bx2

  1. Express as a continued fraction.
  1. Write down its convergents.
    The convergents are:
    • First: ,
    • Second: ,
    • Third: .

iii. Use the extended Euclidean algorithm to find and one integer solution to the Diophantine equation .

Compute using the Euclidean Algorithm

The last non-zero remainder is:

Work Backwards to Find the Linear Combination

We now express as a linear combination of and .

  • Start with the second-to-last equation:

  • Substitute into the equation:

  • Substitute into the equation:

  • Substitute into the equation:

  • Substitute into the equation:

The , and one solution to is:

General solution:
The general solution to is:
where and are the specific solution found via back-substitution, and is any integer.

Problem 6.

1. Solve the Chinese Remainder Theorem problem step by step:

Solve the system of congruences:

Step 1. Compute the product of the moduli.

Step 2. Compute individual terms and their modular inverses.
Let , where are the individual moduli :

  • For :
    Find such that .
    Using the extended Euclidean Algorithm:
    The inverse is .

  • For :
    Find such that
    Using the extended Euclidean Algorithm:
    The inverse is .

  • For :
    Find such that
    Using the extended Euclidean Algorithm:
    The inverse is .

Step 3. Construct the solution using the Chinese Remainder Theorem formula.
The solution is:
Substitute :
Calculate each term:

  • ,
  • ,
  • .

Add them together:

Simplify modulo :

Thus, the solution is:

2. Adapt the previous question into a word problem for a general audience:

A wizard is trying to hide a magical scroll. The scroll is located such that:

  • When it is divided into groups of 7, there are 4 remaining scrolls.
  • When it is divided into groups of 8, there are 3 remaining scrolls.
  • When it is divided into groups of 9, there are 2 remaining scrolls.

Where is the scroll located? To calculate this, use the magic formula:
where , and .

Replace with any other numbers , and solve for .

Table Of Contents
AAM-HW-2
Problem 1.
Problem 2. Homogeneous Linear Recurrence with constant coefficients
i. Write down an equation for , and find all solutions for in terms of and .
ii. In the case of Fibonacci numbers , what are the two solutions, ?
iii. It is not true that or . Someone now guesses that a linear combination might work:
Problem 3. Combinatorics. Solve one of the following two questions.
i. Mr. Chou is a nunchucks ("dual-section stick") master. He shouts either in "Heng!" (1 beat) or "Ha-Hi!" (2 beats).
Problem 4: Prime Factorization and Euler's Totient Function
Problem 5.
i. Use the Euclidean Algorithm to show that 314 and 159 are coprime.
ii. Use the Euclidean Algorithm to find .
iii. Use the extended Euclidean algorithm to find and one integer solution to the Diophantine equation .
Problem 6.
1. Solve the Chinese Remainder Theorem problem step by step:
2. Adapt the previous question into a word problem for a general audience: