Let x be the least number divisible by 16, 24, 30, 36 and 45, and x is also a perfect square. What is the remainder when x is divided by 123?

Options

A. 100
B. 40
C. 103
D. 33

Answer

To solve the problem, we need to find the least number \( x \) that is divisible by 16, 24, 30, 36, and 45, and also a perfect square. We will follow these steps:

### Step 1: Find the prime factorization of each number.
- \( 16 = 2^4 \)
- \( 24 = 2^3 \times 3^1 \)
- \( 30 = 2^1 \times 3^1 \times 5^1 \)
- \( 36 = 2^2 \times 3^2 \)
- \( 45 = 3^2 \times 5^1 \)

### Step 2: Determine the highest power of each prime factor.
To find the least common multiple (LCM), we take the highest power of each prime factor that appears in the factorizations:
- For \( 2 \): The highest power is \( 2^4 \) (from 16).
- For \( 3 \): The highest power is \( 3^2 \) (from 36 and 45).
- For \( 5 \): The highest power is \( 5^1 \) (from 30 and 45).

### Step 3: Calculate the LCM.
Now, we can calculate the LCM using the highest powers:
\[ \text{LCM} = 2^4 \times 3^2 \times 5^1 \]
Calculating this step-by-step:
- \( 2^4 = 16 \)
- \( 3^2 = 9 \)
- \( 5^1 = 5 \)

Now, multiply these together:
\[ \text{LCM} = 16 \times 9 = 144 \]
\[ \text{LCM} = 144 \times 5 = 720 \]

### Step 4: Ensure \( x \) is a perfect square.
The LCM we found is 720. To make it a perfect square, we need to adjust the powers of the prime factors:
- The prime factorization of 720 is \( 2^4 \times 3^2 \times 5^1 \).
- To make it a perfect square, all prime factors must have even powers.

The current powers are:
- \( 2^4 \) (even)
- \( 3^2 \) (even)
- \( 5^1 \) (odd)

To make \( 5^1 \) even, we need to multiply by \( 5^1 \) (to make it \( 5^2 \)):
\[ x = 720 \times 5 = 3600 \]

### Step 5: Verify that \( x \) is a perfect square.
The prime factorization of 3600 is:
\[ 3600 = 2^4 \times 3^2 \times 5^2 \]
Since all the powers are even, \( 3600 \) is indeed a perfect square.

### Step 6: Find the remainder when \( x \) is divided by 123.
Now we need to calculate \( 3600 \mod 123 \):
\[ 3600 \div 123 \approx 29.268 \quad \text{(take the integer part: 29)} \]
Calculating \( 29 \times 123 \):
\[ 29 \times 123 = 3567 \]
Now, subtract this from 3600 to find the remainder:
\[ 3600 - 3567 = 33 \]

### Final Answer:
The remainder when \( x \) is divided by 123 is \( \boxed{33} \).