Iran Math Olympiad number theory problem | x^13 equals 21982145917308330487013369
Вставка
- Опубліковано 21 тра 2024
- You can leave a comment down below,
like and subscribe to my channel if you like my content.
You can also support me on Ko-fi at ko-fi.com/jiashengjin
A) Last digit of x^(4n+1) is the same as the last digit of x. So we know that the last digit of x has to be 9.
B) 100^13 = 10^26, which is 27 digits long, so we know that x is less than 100.
C) Fermat's little theorem tells us that a^p = a (mod p) for any prime p. Dividing the given number by 13 gives a remainder of 11.
From A, B and C we know that we're looking for a number of the form 13k + 11 < 100 that ends on a 9.
This means that 13k has to end on an 8. Looking at the times table for 13 find 78 = 13*6 as the only one that ends on an 8.
78 + 11 = 89.
x = 89
Very succinct and nice answer. Excellent.
I used A and B like you did, but not C. Since x¹³ ≈ 2.2 × 10²⁵ and 100¹³ = 10²⁶, we know that x must be a bit below 100, but 99 seems too close, so we hypothesize that it is 89. Since 89 is prime (9*10=90, 7*13=91), then if we can show that 89 divides x¹³ then 89 must divide x, which would mean that x = 89 because any multiple would be greater than 100.
There is a relatively easy way to check for divisibility by (10n−1) which avoids long division and only uses multiplication and addition.
n*(10a + b) ≡ (a + nb) mod (10n−1)
and n ≢ 0 mod (10n−1)
so (10a + b) ≡ 0 mod (10n−1) iff (a + nb) ≡ 0 mod (10n−1)
For 89 we have n=9.
So if we start with any number A, then let A′ be the new number formed by erasing the least significant digit of A, and let A″ be 9 times the least significant digit of A added to A′. Then A ≡ 0 mod 89 iff A″ ≡ 0 mod 89. Apply this recursively.
We get the sequence:
21982145917308330487013369 (this is x¹³)
2198214591730833048701417
219821459173083304870204
21982145917308330487056
...
21982199
2198300
2225
267
89
And because the last number is divisible by 89, then all the previous numbers in the sequence are also divisible by 89, including the original number which is x¹³. But that means that x=89, as mentioned in the first paragraph.
9 in odd power ends with 9, so our x ends with 9. Now we need a number that in a power 13 reaches 26 digits. So we drop 13 right digits leaving a number with 13 digits. Now find number that in a power 13 is closest to it. (8^13 = 2^13^3): 2^13=8192, 8192^3 ~ 500000000000 12 digits. So our answer would be 89?
If we know that x is an integer:
x^13 has 26 digits, so x must have 2 digits.
x^13 is an odd number, thus x also has to be odd. The last digit of x cannot be 1 or 5, because then all powers also end in 1 or 5, respectively. Thus the last digit of x must be 3,7 or 9.
3^2 and 7^2 both end in 9, thus 3^4 and 7^4 end in 1, as well as 3^12 and 7^12. Thus 3^13 and 7^13 end in 3 and 7, respectively. Thus the last digit of x must be 9.
It is easy to calculate x^13 mod 3, just add all digits and we find that x^13 mod 3 = 2.
This means x mod 3 = 2 as well. We can exclude 0 and 1, because if x mod 3 was 0 or 1, then all powers of x mod 3 are also 0 or 1, respectively.
Now we know the last digit of x is 9, and x mod 3 = 2. A possible value is x=89. The next smaller value is 59.
x must be a 2-digit number, but it cannot be too small. 60^13 has already fewer than 26 digits: 60^2=3600, 60^4=36^2*10^4=1296*10^4. This is smaller than 13*10^6, thus 60^8 is smaller than 169*10^12, which has only 15 digits, so we already lost one digit, 60^13 can have at most 25 digits, most likely it has not more than 24.
This leaves us with the only possible solution of x=89, since x=59 is already too small.
This is way too complicated. It's a super easy problem:
1. check the last digit, it can only be 9
2. check the remainder mod 9, it's 8
3. check the total digit count, it can only have two digits
therefore it's 89
Ye lol, last digit 9 is also trivial by mod2 and mod5; I guess crt rocks again
x = 13th root of the original number *drops chalk as explosion destroys board*
amazing, i love your vids specially about number theory, keep it up with the good stuff
Rather easy to check that by sheer size x it has to be between 80 and 90 and has to end with 3 7 or 9. Of which only 9 can work. So x is 89.
Amazing!
Once you figured out that 1001 is a multiple of 13, you can calculate x^13 mod 1001 by subtracting multiples of 1001 until the remaining number is smaller than 1001.
For example, subtracting 1001*k*10^n can be achieved by subtracting k simultaneously from the 10^n and the 10^(n+3) digits, i.e. you can subtract (or add) the same amount simultaneously from any two digits that are 3 positions apart from each other. This does not change the remainder when dividing by 1001 (or 13).
For example, if x^13 starts with the digits 21982145..., subtract 2 from the first and the 4th digits, you obtain 1962145.... Then subtract 1 from the 1st and the 4th digit to obtain 961145...
Now next is to subtract 9 from the 1st and 4th digit. If the 4th digit is not large enough, include the 3rd digit: 60245... If you keep doing this 21 times you end up with the remainder 89.
In principle this is just a long division of x^13 by 1001, but the calculation is not difficult, and you don't need to keep track of the result of the division.
I actually guessed the correct answer using a few memorized logarithms:
The base ten logs for 1-10 are approximately
0, 0.3, 0.48, 0.6, 0.7, 0.78, 0.85, 0.9, 0.95, 1
Looking at the big number, it's basically 22x10^24, so its base 10 log is 24 + log(11) + 0.3. The 11 log isn't in the list I memorized, so I used linear interpolation between 12 and 10: log(12) ~ 1.08, so log(11) ~ 1.04.
Then log(big number) ~ 25.34. Dividing by 13 to get the 13th root logarithm, I just do 3 digits mentally to get 1.94. This is extremely close to what I would compute for log(90) ~ 1.95, so my first guess would be that the 13th root of big number is 89.
Use the full cycle of 10 (mod 13), making no additional divisions by 13. We have
10¹ = -3 (mod 13)
10² = -4 (mod 13)
10³ = -1 (mod 13)
10⁴ = 3 (mod 13)
10⁵ = 4 (mod 13)
10⁶ = 1 (mod 13)
The number is
21
982145
917308
330487
013369
Just sum the digits in each column and multiply by the respective value of 10ⁿ, n=0,...,5, (mod 13),
(9+9+3+0)×4
+ (8+1+3+1)×3
+ (2+7+0+3)×(-1)
+ (1+3+4+3)×(-4)
+ (2+4+0+8+6)×(-3)
+ (1+5+8+7+9)×1
= 21×4
+ 13×3
+ 12×(-1)
+ 11×(-4)
+ 20×(-3)
+ 30×1
Mod 13:
= (-5)×4
+ 0×3
+ (-1)×(-1)
+ (-2)×(-4)
+ (-6)×(-3)
+ 4×1
= (-5+2)×4
+ 0
+ 1
+
+ 18
+ 4
= -12
+ 1
+ 5
+ 4
= 1 + 10
= 11
No division of three digit numbers or 6 digit numbers required.
It has to end in 9. So
13k+11 = ...9
This means k ends in 6, so k = 10n+6,
13k+11
= 130n+89
Then it is over. Of course, this reasoning only works because we are assuming the number has an integer 13th root.
Hahaha, I made some silly calculations. Anyways, using the full cycle of 10 male the calculations far easier.
Last digit is 9, it's easy. 80^13 < 10^25, so it can be 99 or 89. If it 99 then the given number mast be divided by 11. Easy to se that it doesn't. So it is only 89
1. Since 100^23 has 27 digits, x must be a two digit number.
2. Last digit of x^(4*3+1) must be same as last digit of x^1, therefore, last digit of x must be 9.
3. Digital sum of the given number is 8, therefore, the digital sum of x^13 must be 8. Solving which we get x=89.
Another approach without using modulo and log (this is "no-pen-no-paper" method):
1. the last digit of x must be 9, because only 9 goes in cycles (9,1) with the 13th power being 9.
2. 100^13 is 27-digit number, so x must be 2-digit number ----> 26(digits) : 13 = 2.
3. x can't be 99, because the given 26-digit number is too small (it's obvious).
4. 8 = (2^3)^13 = 2^39; let's calculate 2^40
5. 2^10 = 1024, let's use "1000"
6. 2^40 = approx. 8^13 = approx 1000 ^4
7. 80^13 = approx 1000 ^4 * 10^13 = 10^12 * 10^13 = 10^25
8. It is less than the given 26-digit number
9. therefore x = 89
Great. At the end you finished a bit quickly.
I counted digits and figured it had to be 2 digit number. Last digit had to be 9. Then I compared to 100 and saw we ended up at 22% of what 100 would have. This means we haved a little over two times so a half life of roughly 6 years. Law of 72 says we are decreasing by 12% per year to have a half life of six years so answer should be close to 88. Since last digit is 9 the answer must be 89.
Oh no finance has tainted modular arithmetic
in the beginning of the video you say x from real numbers. then you can't assume it's an integer
Real numbers encapsulate the integers in this case
@@phlopmeistergenerel find x^3 = 10000, x from real numbers. Then apply all logic as in the video (assuming it's integer): x^3 = x (mod 3). then 10000 mod 3 = 1, then x mod 3 = 1. Possible solutions 1,4,7,10,13,16,19,22,25,28. Because 30^3 = 27000 > 10000
1 obviously doesn't work
4^3 = 4 (mod 10) bad
7^3 = 3 (mod 10) bad
10^3 = 0 (mod 10) looks good
13^3 = 7 (mod 10) bad
16^3 = 6 (mod 10) bad
19^3 = 9 (mod 10) bad
22^3= 8 (mod 10) bad
25^3 = 5 (mod 10) bad
28^3 = 2 (mod 10) bad
the only option which gives correct last digit is 10. *THUS* answer is 10.
This is wrong because we assumed x is integer. Similarly, it's not the fact that your answer is correct. Because *you have to raise answer into 13 power without calculator* to check is it an answer or not. This invalidates requirement to find an answer without using calculator.
I used 10^13 < x^13 < 10^26 -> 10 < x < 100.
Then n^k (mod 10) == n^(k (mod φ(10))
-> n^13 == 9 (mod 10) == n^(13 (mod 4)) -> n == 9 (mod 10)
From there, a binomial expansion gives 90^13 = 10^13 * (10-1)^13
≈ 10^26 - 13*10^25 + 78*10^24 = 52*10^25, whereas
10^26 - 13*10^25 + 78*10^24 - 286*10^23 = 23.4*10^25. The remaining terms are alternating and are decreasing in magnitude, so 90^13 > 2.34×10^26.
Testing 80^13 tells us that 80^13 < 10^26 - 26×10^25 + 312×10^24 - 2288×10^23 + 11440×10^22 ≈ 0.3×10^25, which is too small (calculations might be a little off since I did them in my head). Therefore, since 80
Strangely, x^13 = my phone number multipled by my wife's number plus our door number to the power of the numbers in my post code.
I just thought...
Ends with 9 -> The original number must end with 3, 7, or 9
3 -> Final digits of 3 9 7 1 that repeats itself, will be 3 in 13 (Fail)
7 -> Final digits of 7 9 3 1 that repeats itself, will be 7 in 13 (Fail)
9 -> Final digits of 9 1 that repeats itself, will be 9 in 13 (Success)
There are 26 digits, close to 10^26 with 27 digits (AKA 100^13), but not too close
I'm now left with 89 and 99 as the most likely answers, and thought, "It shouldn't be too close" and picked 89...i was right...
Hello from iran
wow this is crazy
You made some confusion, didn't you? Because you could divide the number in 3 digits, alternating plus and minus ...
Actually, no ... use the full cycle of 10 (mod 13), making no additional divisions by 13. We have
10¹ = -3 (mod 13)
10² = -4 (mod 13)
10³ = -1 (mod 13)
10⁴ = 3 (mod 13)
10⁵ = 4 (mod 13)
10⁶ = 1 (mod 13)
The number is
21
982145
917308
330487
013369
Just sum the digits in each column and multiply by the respective value of 10ⁿ, n=0,...,5, (mod 13),
(9+9+3+0)×4
+ (8+1+3+1)×3
+ (2+7+0+3)×(-1)
+ (1+3+4+3)×(-4)
+ (2+4+0+8+6)×(-3)
+ (1+5+8+7+9)×1
= 21×4
+ 13×3
+ 12×(-1)
+ 11×(-4)
+ 20×(-3)
+ 30×1
Mod 13:
= (-5)×4
+ 0×3
+ (-1)×(-1)
+ (-2)×(-4)
+ (-6)×(-3)
+ 4×1
= (-5+2)×4
+ 0
+ 1
+
+ 18
+ 4
= -12
+ 1
+ 5
+ 4
= 1 + 10
= 11
No division of three digit numbers or 6 digit numbers requires.
It has to end in 9. So
13k+11 = ...9
This means k ends in 6, so k = 10n+6,
13k+11
= 130n+89
Then it is over. Of course this reasoning only works because we are assuming the number has an integer 13th root.
Прикольно
It doesn't go neither from the paper...
(x ➖ 3x+2)
Value of X must be odd, since the result is odd, and X is not 1 or 5 (where the result has unit 1 and 5)
For K=1,2,3,4,5,..., then
?3^K, the unit result is 3,9,7,1,3,9,7,1,...
?7^K, the unit result is 7,9,3,,1,7,9,3,1,...
?9^K the unit result is 9,1,9,1,9,1,9,....
For K=13, then ?3^K has unit 3, ?7^K has unit 7 and ?9^K has unit 9
So, possible answer is 09,19,29,39,49,59,69,79,89,99
Number of digit 99^13 is about 36 (less than 36) so 99 is rejected, then X=88
(** if there is no typo like this 21,982,145,917,038,330,487,013,369 😊😊😊)
Gonna guess like 91?
89
0:08 X is a real number
0:18 X is an integer number
WTF!? How did you figured out (in just 10 seconds) that solution is an integer number?
Not convincing, poorly explained.
10 80, and 9^13 > 80^6 * 9 = 8^6 * 9 * 10^6 > 500^2 * 9 * 10^6, or 25*9 * 10^10, or 2.25*10^12, which is too big.
So y=7 is proven too small, y=9 is proven too big, and y=8 looks plausible.
So the answer is 89.