Showing posts with label modulo. Show all posts
Showing posts with label modulo. Show all posts
Friday, October 5, 2018
Prove square root is irrational
Prove that for any positive integer $n$, then
$$\sqrt{\frac{n}{n+1}}$$
is irrational.
Solution
If $n+1$ is a square then we only need to show that \sqrt{n} is irrational, which amounts to showing that it's not a square. This follows the fact that if $n+1$ and $n$ are both squares then $n=0$, contradicting problem condition.
If $n+1$ is not a square, then it has prime factors with odd powers in $n$. Let $k$ be the largest of such factor and $a$ is its power. Meaning, $k^a | n+1$ but $k^{a+1}$ does not divide $n+1$.
Now suppose there exist $p,q$ relatively prime such that
$$\sqrt{\frac{n}{n+1}}=\frac{p}{q}$$
$$(n+1)p^2 = nq^2$$
Because $k^a | LHS$ then $k^a | RHS$. If $k^a | n$ then $k | (n+1)-n = 1$, a contradiction (because $k$ is a prime).
And because $k$ is prime then $k^a | q^2$ which means $k^{a+1} | q^2$ (because $a$ is odd). This means that $k$ divides $p$, contradicting our assumption that $p,q$ are relatively prime.
Thursday, August 11, 2016
Polynomial and divisibility
Find an integer polynomial $P(x)$ with the lowest degree that satisfies the following:
$P(x)$ is divisible by $x^2+x+1$
$P(x)+3$ is divisible by $x^{2017} -1$
Solution
Let $Q(x) = x^2+x+1$ and $R(x) = x^{2016} + \dots + 1$. It's easy to show that $Q$ and $R$ are relatively prime.
The LCM for both divisors is thus $(x-1)Q(x)R(x)$ which has degree 2019.
Now if $P$ and $P'$ both satisfy the problem statement, then $P-P'$ must be divisible by $(x-1)Q(x)R(x)$.
On the other hand, if $P$ satisfies the problem statement, then $P + A(x).(x-1)Q(x)R(x)$ also satisfies the problem statement for any integer polynomial $A(x)$.
Therefore, we can find at most one $P(x)$ with degree less than 2019, because if there were two such polynomials, their difference must be divisible by $(x-1)Q(x)R(x)$ but that difference has degree less than 2019, so the difference must be zero. That one polynomial is our answer.
To find it: let $t$ be the root of $Q(x)$. We want to find $P(x)$ such that:
$$P(x)+3 = S(x).(x-1).R(x)$$ for some $S(x)$, with $S(x) = ax+b$. We know that it's possible for $S$ to be a linear function because we've established that there exists a $P$ with degree less than 2019, and $R$ has degree 2016.
$$P(t) + 3 = (at+b).(t-1).R(t)$$
$P(t) = 0$ because $P(x)$ is divisible by $Q(x)$ and $Q(t) = 0$.
$R(t) = t^{2016} + \dots + t + 1 = 1$ because every 3 consecutive terms in $t^{2016} + \dots + t$ sum to zero (because $Q(t) = 0$).
So:
$$ 3 = (at+b)(t-1)$$
$$at^2 + (b-a)t - b-3 = 0$$
$$a(-t-1) + (b-a)t - b-3 = 0$$
$$ (b-2a)t=a+b+3$$
Solving for the system:$b-2a = 0, a+b+3 = 0$ gives us: $a = -1, b= -2$ so $S(x) = -(x+2)$
Plugging in to the equations, we find:
$$P(x) = -(x+2)(x^{2017}-1) - 3 = -x^{2018} - 2x^{2017} + x -1 = -x^2(x^{2016}-1) -2x(x^{2016}-1) -( x^2+x+1) $$
Each term in the right-most expression is divisible by $Q(x)$ because $(x^{2016}-1)$ is divisible by $x^3-1$ so $P(x)$ is also divisible by $Q(x)$
Thursday, April 5, 2012
Teacher distributing coupons
Let $n$ be a positive integer, and $N = n(n+1)(2n+1)$. In a class with $N$ students, each student has an ID number from $1$ to $N$. The teacher then gives each student red, green, and blue coupons as follows:
A student with id $k$ will receive $x$ red coupons, $y$ green groupons, $z$ blue coupons where
$1 \leq x \leq n, n | k-x$
$1 \leq y \leq n+1, (n+1) | k-y$
$1 \leq z \leq 2n+1, (2n+1) | k-z$.
For each student then the teacher gives him a penny based on the median number of coupons he receives. For example, if a student receives 2 red, 4 green, and 5 blue coupons, he gets 4 cents. If another student receives 2 red, 5 green, and 4 blue, he also gets 4 cents. If yet another student get 3 red, 5 green, 5 blue, he gets 5 cents.
Find the total number of money that the teacher has to pay to the entire class.
Solution
Note that $n, n+1, 2n+1$ are all pairwise prime, and $N$ is their LCM. By Chinese Remainder Theorem, we find that for each triplet $(x,y,z)$ such that $1 \leq x \leq n, 1 \leq y \leq n+1, 1 \leq z \leq 2n+1$, there is exactly one $k$ such that $1 \leq k \leq N, k \equiv x \mod N, k \equiv y \mod N, k \equiv z \mod N$. In other words, for each triplet of $(x,y,z)$ within the allowable coupon range, there is exactly one student who receives $x$ red, $y$ green, and $z$ blue coupons.
Solution 1
We divide the cases based on the amount of money a particular student receives. Suppose a student receives $k$ cents.
Case 1: $1 \leq k \leq n$.
Let $x,y,z$ be the number of red, green, and blue coupons he receives.
Case 1a: $x,y,z$ are all distinct.
If $x < y < z$, then $k = y$. For a student to be paid $k$ cents in this manner, $x$ must be from 1 to $k-1$, and $z$ must be from $k$ to $2n+1$, inclusive. Conversely, as long as $x$ is any value from $1$ to $k-1$, and $z$ is any value from $k+1$ to $2n+1$, then $(x,y,z)$ form a triple where the median is $k$. For each of these triples, there is exactly one student who gets paid $k$ cents. So the number of students who gets paid $k$ cents in this manner is $(k-1)(2n+1-k)$, so the total money spent on them is $k(k-1)(2n+1-k)$
Since $k$ is allowed to take range from $1$ to $n$, then the number of students who gets paid via $x < y < z$ configuration is
$$\sum_{k=1}^{n} k(k-1)(2n+1-k)$$
Now, that's just for $x < y < z$. There are 6 permutations of order, and we can repeat the same analysis for each. The total number or $x,y,z$ all distinct is:
$$2 \sum_{k=1}^{n} k(k-1)(n-k) + 2 \sum_{k=1}^{n} k(k-1)(n+1-k) + 2 \sum_{k=1}^{n} k(k-1)(2n+1-k)$$
$$ = 2 \sum_{k=1}^{n} k(k-1)(4n+2-3k) $$
Case 1b: two of them are the same, the third higher.
Suppose $x=y < z$, then $k = x = y$. Similar analysis as above, the number of students who gets paid this way is $(2n+1-k)$, and the total money spent on them is $k(2n+1-k)$. Summing from $k=1$ to $n$, and also taking into account cases of $x=z < y, y=z < x$, we have:
$$\sum_{k=1}^{n} k (4n+2-3k)$$
Case 1c: two of them are the same, the third lower.
Suppose $x < y= z$, then $k = y = z$. Again, the number of students is $k-1$, so total amount of money, including cases of $y < x= z, z < x=y$ is:
$$ 3 \sum_{k=1}^{n} k(k-1)$$
Case 1d: $x=y=z$
$$\sum_{k=1}^{n} k$$
Case 2: $k = n+1$.
Since $x \leq n$, then $x$ cannot be the median nor the top, and $y$ cannot be on top, so the only configuration left is $x < y \leq z$. There are $n$ values for $x$ and $n+1$ values for $z$ (from $n+1$ to $2n+1$). So the number of students is $n(n+1)$ and total amount paid is $n(n+1)^2$
These are all the cases, since the median cannot be greater than $n+1$. Summing over all the sums, we have:
(do the algebra here)
Solution 2:
We divide cases based on the range of $x,y,z$.
Case 1: $1 \leq x,y,z \leq n$
Recall that each triplet $(x,y,z)$ corresponds to exactly one student. We form student pairs as follows: student who receives $(x,y,z)$ is paired with the student who receives $(n+1-x, n+1-y, n+1-z)$. Note that if $n$ is even, then each student gets a pair, but if $n$ is odd, there is a student $((n+1)/2, (n+1)/2, (n+1)/2$ who is paired with himself.
Suppose student $A$ and student $B$ is a pair. Note that if $x < y < z$, then $n+1-x > n+1-y > n+1-z$, so if $A$ gets paid $y$, then $B$ gets paid $n+1-y$. The sum of payment from this pair is $n+1$. It's easy to check that this rule holds for all order configurations ($x = y < z, x < y = z$, etc). In other words, the average income of this pair is $(n+1)/2$. This holds for all pairs, even in the case where a student is paired to himself. The total amount of income for all students in this group is then $n^3 (n+1)/2$.
Case 2: $1 \leq x,y \leq n, z = n+1$.
In this case, since $z$ is the largest of all three, then the median is $\max(x,y)$, summed over all $1 \leq x,y \leq n$.
Case 2a: $x > y$.
Then $\max (x,y) = x$. For each $x$, there are $x-1$ possible values of $y$, meaning there are $x-1$ students, each of which are getting paid $x$ cents. So the total income here is:
$$\sum_{k=1}^{n} k(k-1)$$
Case 2b: $x < y$
By symmetry, it's identical to 2a.
Case 2c: $x = y$.
The total income here is $\sum_{k=1}^{n} k$
Case 3: $1 \leq x,z \leq n, y = n+1$.
By symmetry, it's identical to case 2
Case 4: $1 \leq x \leq n, y = z = n+1$.
The median here is $n+1$, and there are $n$ students, so total income here is $n(n+1)$.
Case 5: $1 \leq x \leq n, y = n+1, z > n+1$
The median here is $n+1$, and there are $n^2$ students, so total income is $n^2(n+1)$.
Case 6: $1 \leq x,y \leq n, z > n+1$
This case is similar to case 2. In fact, EACH value of $z$ is identical to case 2 in that we're summing $\max (x,y)$ over all $1 \leq x,y \leq n$. Case 6 is thus like $n$ instances of case 2.
A student with id $k$ will receive $x$ red coupons, $y$ green groupons, $z$ blue coupons where
$1 \leq x \leq n, n | k-x$
$1 \leq y \leq n+1, (n+1) | k-y$
$1 \leq z \leq 2n+1, (2n+1) | k-z$.
For each student then the teacher gives him a penny based on the median number of coupons he receives. For example, if a student receives 2 red, 4 green, and 5 blue coupons, he gets 4 cents. If another student receives 2 red, 5 green, and 4 blue, he also gets 4 cents. If yet another student get 3 red, 5 green, 5 blue, he gets 5 cents.
Find the total number of money that the teacher has to pay to the entire class.
Solution
Note that $n, n+1, 2n+1$ are all pairwise prime, and $N$ is their LCM. By Chinese Remainder Theorem, we find that for each triplet $(x,y,z)$ such that $1 \leq x \leq n, 1 \leq y \leq n+1, 1 \leq z \leq 2n+1$, there is exactly one $k$ such that $1 \leq k \leq N, k \equiv x \mod N, k \equiv y \mod N, k \equiv z \mod N$. In other words, for each triplet of $(x,y,z)$ within the allowable coupon range, there is exactly one student who receives $x$ red, $y$ green, and $z$ blue coupons.
Solution 1
We divide the cases based on the amount of money a particular student receives. Suppose a student receives $k$ cents.
Case 1: $1 \leq k \leq n$.
Let $x,y,z$ be the number of red, green, and blue coupons he receives.
Case 1a: $x,y,z$ are all distinct.
If $x < y < z$, then $k = y$. For a student to be paid $k$ cents in this manner, $x$ must be from 1 to $k-1$, and $z$ must be from $k$ to $2n+1$, inclusive. Conversely, as long as $x$ is any value from $1$ to $k-1$, and $z$ is any value from $k+1$ to $2n+1$, then $(x,y,z)$ form a triple where the median is $k$. For each of these triples, there is exactly one student who gets paid $k$ cents. So the number of students who gets paid $k$ cents in this manner is $(k-1)(2n+1-k)$, so the total money spent on them is $k(k-1)(2n+1-k)$
Since $k$ is allowed to take range from $1$ to $n$, then the number of students who gets paid via $x < y < z$ configuration is
$$\sum_{k=1}^{n} k(k-1)(2n+1-k)$$
Now, that's just for $x < y < z$. There are 6 permutations of order, and we can repeat the same analysis for each. The total number or $x,y,z$ all distinct is:
$$2 \sum_{k=1}^{n} k(k-1)(n-k) + 2 \sum_{k=1}^{n} k(k-1)(n+1-k) + 2 \sum_{k=1}^{n} k(k-1)(2n+1-k)$$
$$ = 2 \sum_{k=1}^{n} k(k-1)(4n+2-3k) $$
Case 1b: two of them are the same, the third higher.
Suppose $x=y < z$, then $k = x = y$. Similar analysis as above, the number of students who gets paid this way is $(2n+1-k)$, and the total money spent on them is $k(2n+1-k)$. Summing from $k=1$ to $n$, and also taking into account cases of $x=z < y, y=z < x$, we have:
$$\sum_{k=1}^{n} k (4n+2-3k)$$
Case 1c: two of them are the same, the third lower.
Suppose $x < y= z$, then $k = y = z$. Again, the number of students is $k-1$, so total amount of money, including cases of $y < x= z, z < x=y$ is:
$$ 3 \sum_{k=1}^{n} k(k-1)$$
Case 1d: $x=y=z$
$$\sum_{k=1}^{n} k$$
Case 2: $k = n+1$.
Since $x \leq n$, then $x$ cannot be the median nor the top, and $y$ cannot be on top, so the only configuration left is $x < y \leq z$. There are $n$ values for $x$ and $n+1$ values for $z$ (from $n+1$ to $2n+1$). So the number of students is $n(n+1)$ and total amount paid is $n(n+1)^2$
These are all the cases, since the median cannot be greater than $n+1$. Summing over all the sums, we have:
(do the algebra here)
Solution 2:
We divide cases based on the range of $x,y,z$.
Case 1: $1 \leq x,y,z \leq n$
Recall that each triplet $(x,y,z)$ corresponds to exactly one student. We form student pairs as follows: student who receives $(x,y,z)$ is paired with the student who receives $(n+1-x, n+1-y, n+1-z)$. Note that if $n$ is even, then each student gets a pair, but if $n$ is odd, there is a student $((n+1)/2, (n+1)/2, (n+1)/2$ who is paired with himself.
Suppose student $A$ and student $B$ is a pair. Note that if $x < y < z$, then $n+1-x > n+1-y > n+1-z$, so if $A$ gets paid $y$, then $B$ gets paid $n+1-y$. The sum of payment from this pair is $n+1$. It's easy to check that this rule holds for all order configurations ($x = y < z, x < y = z$, etc). In other words, the average income of this pair is $(n+1)/2$. This holds for all pairs, even in the case where a student is paired to himself. The total amount of income for all students in this group is then $n^3 (n+1)/2$.
Case 2: $1 \leq x,y \leq n, z = n+1$.
In this case, since $z$ is the largest of all three, then the median is $\max(x,y)$, summed over all $1 \leq x,y \leq n$.
Case 2a: $x > y$.
Then $\max (x,y) = x$. For each $x$, there are $x-1$ possible values of $y$, meaning there are $x-1$ students, each of which are getting paid $x$ cents. So the total income here is:
$$\sum_{k=1}^{n} k(k-1)$$
Case 2b: $x < y$
By symmetry, it's identical to 2a.
Case 2c: $x = y$.
The total income here is $\sum_{k=1}^{n} k$
Case 3: $1 \leq x,z \leq n, y = n+1$.
By symmetry, it's identical to case 2
Case 4: $1 \leq x \leq n, y = z = n+1$.
The median here is $n+1$, and there are $n$ students, so total income here is $n(n+1)$.
Case 5: $1 \leq x \leq n, y = n+1, z > n+1$
The median here is $n+1$, and there are $n^2$ students, so total income is $n^2(n+1)$.
Case 6: $1 \leq x,y \leq n, z > n+1$
This case is similar to case 2. In fact, EACH value of $z$ is identical to case 2 in that we're summing $\max (x,y)$ over all $1 \leq x,y \leq n$. Case 6 is thus like $n$ instances of case 2.
Thursday, July 21, 2011
Sequence modulo 2011
A sequence of integers $a_1, \dots, a_{2010}$ satisfy the following properties:
$a_1 - 1$ is divisible by 2011
$a_k a_{k-1} - k$ is divisible by 2011 for $k = 2, 3, \dots, 2010$
Show that $a_{2010} + 1$ is divisible by 2011.
Solution
First we prove the following assertion:
For $k$ odd, then $a_k.2.4.6. \cdots.(k-1) - 1.3.5.\cdots.k$ is divisible by 2011.
For $k$ even, then $a_k.1.3.5. \cdots .(k-1) - 2.4.6.\cdots.k$ is divisible by 2011.
Proof by induction. It can easily be seen for $k=1$ it's true. For $k=2$, we have $2011 | a_2a_1 - 2 = a_2(a_1-1) + (a_2-2)$ So $2011 | a_2 - 2$
Suppose it's true for $k-1$ odd, then for $k$ even:
$2011 | a_k a_{k-1} - k$ which means
$$2011 | 2.4.\cdots.(k-2) (a_k a_{k-1} - k) = 2.4.\cdots.(k-2)a_k a_{k-1} - 2.4.\cdots.(k-2).k$$
$$2011 | a_k (2.\cdots.(k-2)a_{k-1} - 1.3.\cdots.(k-1)) + (a_k.1.3.\cdots.(k-1) - 2.\cdots.(k-2).k)$$
And since 2011 divides the first term by induction hypothesis, then it also divides the second term, which completes the induction step. The proof for $k-1$ even and $k$ odd is similar.
Now, that means for $k=2010$, let $X = a_{2010}$ we have:
$$2011 | X.1.3. \cdots .2009 - 2.4.\cdots.2010$$
We now prove the following assertion for $i = 1,2,\dots,1005$
$$2011 | X.1.3. \cdots. (2011-2i) + (-1)^i (2i) (2i+2)\cdots.2010$$
For $i = 1$ it is true by definition. Now suppose it's true for $i-1$, then for $i > 1$:
$$2011 | X.1.3. \cdots. (2011 - 2i).(2011-2i+2) +(-1)^{i-1} (2i-2) (2i)\cdots.2010$$
if $2011 | a(2011+b) + c$ then $2011 | ab+c$
$$2011 | X.1.3. \cdots. (2011 - 2i).(-2i+2) + (-1)^{i-1} (2i-2) (2i)\cdots.2010$$
if $2011 | a$ then $2011 | -a$.
$$2011 | X.1.3. \cdots. (2011 - 2i).(2i-2) + (-1)^{i} (2i-2) (2i)\cdots.2010$$
$$2011 | 2(i-1)(X.1.3. \cdots. (2011 - 2i).+ (-1)^{i} (2i)\cdots.2010)$$
if $2011 | 2(i-1)a$ then $2011 | a$ since 2011 is prime and $i > 1$.
So the assertion holds for $i = 1,\dots, 1005$. Particularly, for $i = 1005$ we have:
$$2011 | X - 2010$$
$$2011 | X + 1 - 2011$$
$$2011 | X + 1$$
$a_1 - 1$ is divisible by 2011
$a_k a_{k-1} - k$ is divisible by 2011 for $k = 2, 3, \dots, 2010$
Show that $a_{2010} + 1$ is divisible by 2011.
Solution
First we prove the following assertion:
For $k$ odd, then $a_k.2.4.6. \cdots.(k-1) - 1.3.5.\cdots.k$ is divisible by 2011.
For $k$ even, then $a_k.1.3.5. \cdots .(k-1) - 2.4.6.\cdots.k$ is divisible by 2011.
Proof by induction. It can easily be seen for $k=1$ it's true. For $k=2$, we have $2011 | a_2a_1 - 2 = a_2(a_1-1) + (a_2-2)$ So $2011 | a_2 - 2$
Suppose it's true for $k-1$ odd, then for $k$ even:
$2011 | a_k a_{k-1} - k$ which means
$$2011 | 2.4.\cdots.(k-2) (a_k a_{k-1} - k) = 2.4.\cdots.(k-2)a_k a_{k-1} - 2.4.\cdots.(k-2).k$$
$$2011 | a_k (2.\cdots.(k-2)a_{k-1} - 1.3.\cdots.(k-1)) + (a_k.1.3.\cdots.(k-1) - 2.\cdots.(k-2).k)$$
And since 2011 divides the first term by induction hypothesis, then it also divides the second term, which completes the induction step. The proof for $k-1$ even and $k$ odd is similar.
Now, that means for $k=2010$, let $X = a_{2010}$ we have:
$$2011 | X.1.3. \cdots .2009 - 2.4.\cdots.2010$$
We now prove the following assertion for $i = 1,2,\dots,1005$
$$2011 | X.1.3. \cdots. (2011-2i) + (-1)^i (2i) (2i+2)\cdots.2010$$
For $i = 1$ it is true by definition. Now suppose it's true for $i-1$, then for $i > 1$:
$$2011 | X.1.3. \cdots. (2011 - 2i).(2011-2i+2) +(-1)^{i-1} (2i-2) (2i)\cdots.2010$$
if $2011 | a(2011+b) + c$ then $2011 | ab+c$
$$2011 | X.1.3. \cdots. (2011 - 2i).(-2i+2) + (-1)^{i-1} (2i-2) (2i)\cdots.2010$$
if $2011 | a$ then $2011 | -a$.
$$2011 | X.1.3. \cdots. (2011 - 2i).(2i-2) + (-1)^{i} (2i-2) (2i)\cdots.2010$$
$$2011 | 2(i-1)(X.1.3. \cdots. (2011 - 2i).+ (-1)^{i} (2i)\cdots.2010)$$
if $2011 | 2(i-1)a$ then $2011 | a$ since 2011 is prime and $i > 1$.
So the assertion holds for $i = 1,\dots, 1005$. Particularly, for $i = 1005$ we have:
$$2011 | X - 2010$$
$$2011 | X + 1 - 2011$$
$$2011 | X + 1$$
Sunday, June 12, 2011
Supersum
For a natural number $n$, the supersum of $n$ is defined as the sum of possible combinations that we can obtain by deleting digits of $n$, calculated as modulo 9. For example, the supersum of 1234 is:
No deletions: 1234 +
Deleting 1 digit: 123 + 134 + 234 + 124
Deleting 2 digits: 12 + 13 + 14 + 23 + 24 + 34 +
Deleting 3 digits: 1 + 2 + 3 + 4
$ = 8 \mod 9$
If $n$ is a 2011-digit number, and $s$ is its supersum, show that $s-n$ is divisible by 9.
No deletions: 1234 +
Deleting 1 digit: 123 + 134 + 234 + 124
Deleting 2 digits: 12 + 13 + 14 + 23 + 24 + 34 +
Deleting 3 digits: 1 + 2 + 3 + 4
$ = 8 \mod 9$
If $n$ is a 2011-digit number, and $s$ is its supersum, show that $s-n$ is divisible by 9.
Monday, August 9, 2010
Number of solutions to modular equation
Prove that there are infinitely many prime numbers $p$ such that there are exactly $p^2$ integer triples $(x,y,z)$ such that $0 \leq x,y,z < p$ and $x^2+y^2 - 2010z^3$ is divisible by $p$.
Solution
We will first show that any prime that has form $p = 6k-1$ and does not divide 2010 satisfies the given condition.
First, let $p$ be such prime. Suppose there are $a,b \in \{ 1, \dots, p-1 \}$ such that $a^3 \equiv b^3 \mod p$.
Since $b^{p-1} \equiv 1 \mod p$ then let $c \equiv ab^{p-2} \mod p$, so that we have $bc \equiv a \mod p$.
Then $b^3c^3 \equiv a^3 \equiv b^3 \mod p$ which means $b^3c^3 \equiv b^3 \mod p$ which then means $c^3 \equiv 1 \mod p$ (since $(b,p) = 1$).
Because $c^{p-1} = c^{6k-2} \equiv 1 \mod p$ and $c^{6k-3} = c^{3(2k-1)} \equiv 1 \mod p$, then we must have $c \equiv 1 \mod p$, which means $a \equiv b \mod p$.
In summary, we've shown that $a^3 \equiv b^3 \Rightarrow a \equiv b \mod p$. This means that the set $\{1^3, \dots, p^3 \} \mod p$ is the same as set $\{ 1, \dots, p \} \mod p$. So given any arbitrary $x$ and $y$, we can find exactly one $z$ such that $z^3 \equiv 2010^{-1} (x^2+y^2) \mod p$. Since there are $p^2$ possible pairs for $(x,y)$, then there are also $p^2$ possible triples for $(x,y,z)$.
Now we show that there are infinitely many primes of the form $6k-1$ which would mean that there must be infinitely many primes of the form $6k-1$ that do not divide 2010.
Note that any prime above 3 must have form $6k+1$ or $6k-1$. If there are only finite number of primes of the form $6k-1$, say $p_1, p_2, \dots, p_n$, consider the number $N = 6p_1p_2 \dots p_n - 1$.
For each $i$, $p_i$ does not divide $N$ because otherwise $p_i$ would also have to divide 1, a contradiction. So $N$ is not divisible by any of the $p_i$s, which means all prime factors of $N$ must be of the form $6k+1$. That means, $N \equiv 1 \mod 6$, a contradiction.
Solution
We will first show that any prime that has form $p = 6k-1$ and does not divide 2010 satisfies the given condition.
First, let $p$ be such prime. Suppose there are $a,b \in \{ 1, \dots, p-1 \}$ such that $a^3 \equiv b^3 \mod p$.
Since $b^{p-1} \equiv 1 \mod p$ then let $c \equiv ab^{p-2} \mod p$, so that we have $bc \equiv a \mod p$.
Then $b^3c^3 \equiv a^3 \equiv b^3 \mod p$ which means $b^3c^3 \equiv b^3 \mod p$ which then means $c^3 \equiv 1 \mod p$ (since $(b,p) = 1$).
Because $c^{p-1} = c^{6k-2} \equiv 1 \mod p$ and $c^{6k-3} = c^{3(2k-1)} \equiv 1 \mod p$, then we must have $c \equiv 1 \mod p$, which means $a \equiv b \mod p$.
In summary, we've shown that $a^3 \equiv b^3 \Rightarrow a \equiv b \mod p$. This means that the set $\{1^3, \dots, p^3 \} \mod p$ is the same as set $\{ 1, \dots, p \} \mod p$. So given any arbitrary $x$ and $y$, we can find exactly one $z$ such that $z^3 \equiv 2010^{-1} (x^2+y^2) \mod p$. Since there are $p^2$ possible pairs for $(x,y)$, then there are also $p^2$ possible triples for $(x,y,z)$.
Now we show that there are infinitely many primes of the form $6k-1$ which would mean that there must be infinitely many primes of the form $6k-1$ that do not divide 2010.
Note that any prime above 3 must have form $6k+1$ or $6k-1$. If there are only finite number of primes of the form $6k-1$, say $p_1, p_2, \dots, p_n$, consider the number $N = 6p_1p_2 \dots p_n - 1$.
For each $i$, $p_i$ does not divide $N$ because otherwise $p_i$ would also have to divide 1, a contradiction. So $N$ is not divisible by any of the $p_i$s, which means all prime factors of $N$ must be of the form $6k+1$. That means, $N \equiv 1 \mod 6$, a contradiction.
Tuesday, March 23, 2010
Happy Saint Math Trick's Day
This problem is inspired by this comic.
Prove that the trick in the comic always works. In other words, if $p$ is a prime number greater than 3, prove that $p^2 + 14 \equiv 3 \mod 12$
Solution: http://dharmath.blogspot.com/2010/03/solution-happy-saint-math-tricks-day.html
Prove that the trick in the comic always works. In other words, if $p$ is a prime number greater than 3, prove that $p^2 + 14 \equiv 3 \mod 12$
Solution: http://dharmath.blogspot.com/2010/03/solution-happy-saint-math-tricks-day.html
Thursday, December 17, 2009
Solution: Stones and Marbles
Original problem: here
First, I apologize that the problem was not carefully worded. The problem statement should have been: find all initial conditions where it's always possible for Bob to empty all the three boxes.
There are 3 boxes, and 2010 stones and 2010 marbles are put arbitrarily inside those three boxes.
At each step, Bob is allowed to either:
1. take a stone from one box, a marble from another box, and put them on the third box
2. add or subtract all boxes by the same number of stones
3. add or subtract all boxes by the same number of marbles
Prove or disprove, that by repeating these steps, Bob can empty all three boxes.
First, I apologize that the problem was not carefully worded. The problem statement should have been: find all initial conditions where it's always possible for Bob to empty all the three boxes.
There are 3 boxes, and 2010 stones and 2010 marbles are put arbitrarily inside those three boxes.
At each step, Bob is allowed to either:
1. take a stone from one box, a marble from another box, and put them on the third box
2. add or subtract all boxes by the same number of stones
3. add or subtract all boxes by the same number of marbles
Prove or disprove, that by repeating these steps, Bob can empty all three boxes.
Tuesday, September 8, 2009
Subscribe to:
Posts (Atom)