This topic contains 12 replies, has 2 voices, and was last updated by 
-
Posts
-
MathJax TeX Test Page
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. Let $P=2^12^22^3…..2^{10}$, find the remainder when $P$ is divided by $7$.
2. $a^2$ leaves a remainder of $1$ when divided by $13$ where $a$ is an integer, find the number of such $a$ that are between $0$ and $100$. Does this generalize to any prime $p$ instead of $13$. What about composite numbers $n$?
3. Prove that $1+2+…+n=\frac{n(n+1)}{2}$ where $n$ is an integer. Since the sum of a bunch of integers is an integer, why is $\frac{n(n+1)}{2}$ necessarily an integer even though there is a fraction divided by $2$. Do a similar proof for $1^2+2^2+….+n^2=\frac{n(n+1)(2n+1)}{6}$ where $n$ is still an integer.
4. How many pairs of primes $p,q$ satisfy the equation $p+q=10^{1234}+1$. If primes $p,q$ have a different remainder when divided by $3$ and $p+q=3^{10}+1$, find all pairs of primes $p,q$.
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!
Anton1. P = 2^(1+2+3…10)=2^(55). We can look for a pattern for the remainders of powers of 2 when they are divided by 7.
2^1/7:R2
2^2/7:R4
2^3/7:R1
2^4/7:R2
2^5/7:R4
2^6/7:R1
We can see that the pattern goes 2,4,1,2,4,1…. Since the remainder of 55/3 is 1, so the remainder would be the first in the pattern, so our answer is 2.Very good job Anton with your explanation and solution! I will not confirm whether your answer is right or wrong but you get 10 points for a clear solution!
Anton3. We can name sequence A to be 1+2+3+…n.
We can arrange 2A as (1+n) + (2+n-1) + (3+n-2)….(n+1), and it simplifies to (1+n) + (1+n) + (1+n) + (1+n)…(1+n), a total of n times. So, 2A = n(n+1). To get A, we can divide by 2 to get A = n(n+1)/2. I am not sure how to prove the sum of squares, though.
MathJax TeX Test Page
Good proof of the formula $1+2+…+n=\frac{n(n+1)}{2}$ but the main task for the problem was to prove that $\frac{n(n+1)}{2}$ is always an integer even though there is a fraction over $2$. For $S_{n}=1^2+2^2+…+n^2$ consider the fact that $S_{n+1}-S_{n}=(n+1)^2$. If you can’t prove the sum of squares formula, then just show that $\frac{n(n+1)(2n+1)}{6}$ is always an integer for integer $n$.
-
This reply was modified 3 years, 2 months ago by
admin.
Yash AgarwalFor proving that n(n+1)/2 is an integer, you take if cases. If n is o mod 2, then it would obviously be an integer since anything multiplied by 0 is 0. But, if n is 1 mod 2, then (n+1) is equal to 2 mod 2 which is equal to 0 mod 2, making the division by 2 an integer.
For proving that n(n+1)(2n+1)/6 is an integer, we first have to take cases and find a pattern. Let’s suppose n mod 6 is equal to 0. Then the rest would obviously be divisible by 6, making it an integer. But, if n = 1 mod 6, then (n+1) is equal to 2 mod 6 and 2n+1 is equal to 3 mod 3. 1*2*3 mod 6 = 6 mod 6 = 0 mod 6, which means it would be divisible by 6, making it an integer. Similarly, if n equals 2 mod 6, then n+1 equal to 3 mod 6 and 2n+1 is equal to 5 mod 6. 2*3*5 mod 6 = 30 mod 6 = 0 mod 6, which means that it would be an integer. It is the same for all values of n up to 5. They all make 0 mod 6, which means that it will always be an integer!
This response is written by Yash Agarwal.
Yash AgarwalMy previous response is for #3, by the way.
Yash Agarwal#2:
Here are some of the mod rules needed for this problem:
If a is equal to b (mod m), then:
a + c = b + c (mod m)
a^c = b^c (mod m)
In this case we are using mod 13, so we know that m would equal 13.
Now, let’s start with some of the easy things. The easiest square mod 13 equals 1 would be 1. 1^2 = 1. And, -1^2 is also equal to 1. So, by using the addition mod rule above, we can get:
1 + 0 = 1 + 13 (mod 13)
1 = 14 (mod 13)
Now, you might be thinking, this is a, not a^2. But, it would be the same thing for a^2. But, using the exponential rule above, we get:
1^2 = 14^2 (mod 13)
1 = 196 (mod 13)It is the same thing for a^2. So, you just have to keep on adding 13 until you get a value of a which exceeds 100. So, those numbers would be:
From -1: 12, 25, 38, 51, 64, 77, 90
From 1: 1, 14, 27, 40, 53, 66, 79, 92Since -1 is not from 0 to 100, -1 would not be included in this case. So, there is a total of 15 possible numbers for a.
Any prime or composite mod would word since the mod doesn’t matter. The rule states … (mod m). M can be prime or composite.
This response is written by Yash Agarwal.
MathJax TeX Test Page
Actually, Yash your answer is partially correct because it is true that the solutions to $x^2 \equiv 1 \bmod 13$ are only $x \equiv 1,-1 \bmod 13$. However, your proof is incorrect and this may not generalize to all moduli other than $13$. For example, notice that $x^2 \equiv 1 \bmod 15$ also has solutions $x \equiv 4,-4,1,-1 \bmod 15$ so there is some issue with your work. Nonetheless, great start and you have been awarded 15 points, 5 points for this problem and 10 points for the other one.
AntonI don’t really understand #4.
p and q are primes, and p+q = 10^1234 +1. However, 10^1234+1 is odd, so it must be an even number + odd number. The only even prime is 2, so the only possible pair would be if p or q = 2, right?
AntonI forgot to do that part of #3, so here it is:
The formula was n(n+1)/2, where n is an integer. If n is even, then we can rearrange the formula to (n/2)(n+1), and both factors must be integers. If n is odd, we know that n+1 must be even, so (n)((n+1)/2) has two integer factors. Since n is an integer, it has to be even or odd, and this formula always gives an integer result.Hey Anton,
Your first comment is correct, but make sure to determine if the pair works or not.
Your solution to the second problem is correct as well but remember to also do it for the sum of squares.
Anton4. There would be no pairs, since we know that 10^1234+1 is odd, so one of the primes has to be 2, and the other is 10^1234-1. We can let p = 2, and q = 10^1234-1. p + q = 10^1234+1, which is not equal to 3^10 +1， so there are no pairs that work. Quick, question, how do we show “Not equal to”
-
This reply was modified 3 years, 2 months ago by
Ayush
Vishal