Unique Properties of Integers Advanced Problems Set 2

[adminKeymaster]

Hey Math Circle Students!

Here are the advanced problems for the next $3$ days! These are more difficult than AMC 8 Problems 15-20 but they fit the range of $20-25$ and some are even AMC 10 level. Each of these problems are worth $10$ points for your leaderboard score!

If you don’t understand one of the questions, feel free to post in the questions forum here

1. Find the maximum value of $k$ such that $28^k$ divides $100!$ where the exclamation mark represents the factorial function (e.g. $5!=5*4*3*2*1$ and $4!=4*3*2*1$)

2. Find the number of positive integer $x$ less than $7$ to $x^2 \equiv 2 \bmod 7$. The existence of a solution is surprising because $2$ is not a perfect square. What about the solutions less than $15$ to $x^2 \equiv 1 \bmod 15$? Why is this interesting as well?

3. How many values of $n$ less than $100$ exist such that $1+2+…+n$ is divisible by $n$. What about the number of values of $n$ such that $1^2+2^2+….+n^2$ is divisible by $n$. (NOTE: $1+2+..+n=\frac{n(n+1)}{2}$ and $1^2+2^2+..+n^2=\frac{n(n+1)(2n+1)}{6}$)

Remember that you can post your solutions below to these problems and I will keep a running leaderboards for the top 10 students who participate the most! I especially appreciate the same problem being solved in different ways!

[Yash Agarwal]

#2:

Mod Rules needed for this problem:

If A = B (Mod m), then:

A + C = B + C (Mod m)

A^x = B^x (Mod m)

First, let’s write out the squares of the first 6 positive integers:

1, 4, 9, 16, 25, and 36

So, if x^2 = 2 (mod 7), that means:

x^2 = 9 (mod 7), since the addition rule states that you can add the mod to the number as many times as you like. For example, if a number was x (mod m) then that would be equal to x + m (mod m).

So, we have x^2 = 9 (mod 7)

9 = 3^2

So, we can rewrite this as:

X^2 = 3^2 (mod 7)

So, by the exponential rule, x can equal 3. So, 3 is one of our solutions.

9 + 7 = 16, another one of our perfect squares. So, the other solution is the square root of 16, which is 4. If we keep on adding 7, we would get 23, 30, 37… We have already exceeded 36. So, the only solutions for the first part of this problem are 3 and 4. Wait, shouldn’t -3 and -4 be involved in the solution too? No, because it has to be a positive integer.

The second part of this problem is “What about x^2 = 1 (mod 15)?”

The rules needed for this problem are:

X – C = Y – C (mod m) if X = Y (mod m)

If x^2 = 1(mod 15), that means that x^2 -1 = 0 (mod 15). In other words, x^2-1/15 leaves a remainder of 0, which means that x^2-1 is divisible by 15. X^2 – 1 = (X+1) (X-1). (X+1) – (X – 1) = 2.

The factors of 15 are 1, 3, 5, and 15. We needed factors that are 2 apart. 3 and 5 is the only pair. 3 + 1 = 4. 5 – 1 = 4. 2 + 1 = 3. 2 – 1 = 1. But, since is not a factor, it is not included here, but it is needed. 0 is a multiple of 13. So, if X-1 = 0, that means X can equal 1 too. So, the only solutions for the second part of this problem are 1 and 4.

This is interesting because 4^2 is not 1. 1 is only 1^2 (and (-1)^2, but they only want positive integers here).

This response is written by Yash Agarwal.

[Anton]

1. We know that there will definitely be enough factors of 2 in 100! in 28^k, since every even number has a factor of 2. So, we can just count the number of times that the factor of 7 appears in 100! There are 13 multiples of 7 under 100, but 49 counts for two factors, so there are a total of 14 factors of 7 in 100! So, the maximum value of k is 14.

[Ayush]

Good work Yash and Anton! You both receive 10 points, but Anton what if the number was 1024*7=7168 instead of 28, how would you solve the problem then?

Also, Yash try to do the exploration problem as it will give you more insight on polynomials in modular arithmetic.

[Yash Agarwal]

#3:

For the first part of the problem, if you look at the formula, it is (n(n+1))/2. So, if n is even, then n+1 is odd and vice versa. If n is even, then the formula is equal to:

(n+1) * n/2. This is a factor of n+1, not n. So, that means n has to be odd to make this work. So, the answer is just all the odd numbers until 100. There are 50 odd numbers.

For the second part of this problem, the most obvious possible answer is 1. 1 (mod 1) = 0. The next possible answer is 5, since n+1 is 6 and 6 divides 6 evenly. Then, the next possible number is 9, where 10*9 (mod 2*3(6)) is 0 because 10 (mod 2) = 0 and 9 (mod 3) equals 0. So, the pattern is 1,5,9,13… until 97. That is 25 numbers.

This response is written by Yash Agarwal.

[Author]

Posts