Find its largest prime factor

Рет қаралды 18,599

Күн бұрын

#Math #numbertheory #Factor
In this video we attempt to find the largest prime factor of the number 146419604.
Few interesting facts on divisibility test. I may make a video on these later:
- To check whether 3 is a divisor, check whether 3 divides the sum of its digits.
- To check whether 5 is a divisor, check whether the last digit is 5 or 0
- To check whether 7,11,13 is a divisor, first divide the number by 1001 will help reduce to a smaller number
- To check whether 37 is a divisor, first divide the number by 111 will help reduce to a smaller number
Subscribe @letsthinkcritically !!
------------------------------------------------
I share Maths problems and Maths topics from well-known contests, exams and also from viewers around the world. Apart from sharing solutions to these problems, I also share my intuitions and first thoughts when I tried to solve these problems.
Subscribe: www.youtube.co...
Email me (address in video) your suggestions! lets.think.critically.27@gmail.com

Пікірлер: 48

@giuseppebassi7406 2 жыл бұрын

Since 73 is already a prime factor of the number, the only prime number to be tested is 79, since everyone else would be anyway less than or equal to 73

@russellsharpe288 2 жыл бұрын

But since it turns out that 79 is not a factor of 6869, you would be left not knowing whether 73 or 6869 is the largest prime factor of the original number. You would would still need to confirm that 6869 is prime.

@Deathranger999 2 жыл бұрын

I was a big fan of this problem up until we had to figure out that 6869 was prime…though I understand the difficulty in constructing a Sophie-Germain-type problem like this that reduces even further. Cool idea, but very difficult to execute much better than they did here.

@giuseppebassi7406 2 жыл бұрын

Look at my comment. Basically we have to check only the case 79

@Deathranger999 2 жыл бұрын

@@giuseppebassi7406 I disagree with your comment. If 6869 happened to be something like 13 * 523, and 523 happened to be prime, then it would be a larger prime factor than 73. So we do need to test all of the smaller primes.

@giuseppebassi7406 2 жыл бұрын

@@Deathranger999 ok you are right, i forgot this

@a_llama 3 жыл бұрын

5:23 ive been using flashcards for languages but maybe i should start using them for prime numbers and powers...

@logannathan.p9542 2 жыл бұрын

What is largest prime number now? M51??

@Qermaq 3 жыл бұрын

So the prize goes to whoever knows the most primes by heart, not the best mathematician?

@fix5072 3 жыл бұрын

And who exactly is the best mathematician? The guy with highest IQ? The Man who had biggest impact on maths? It just comes down to experience and creativity

@a_llama 3 жыл бұрын

he's trained for the IMO, it's just a part of his arsenal.

@ashjee5646 3 жыл бұрын

sophie-germain practical application

@theloganator13 3 жыл бұрын

Favorite 7 divisibility rule: ABCD is divisible by 7 if ABC - 2D is divisible by 7. ex: is 1617 divisible by 7? 161 - 14 = 147 = 21*7, so 7 divides 1617. Work iteratively, and for very large numbers! 864192 --> 86415 --> 8631 --> 861 -> 84 = 7*12, so 7 divides 864192. Favorite 11 divisibility rule: ABCD is divisible by 11 if A-B+C-D is divisible by 11. ex: 6237? 6-2+3-7 = 0, so 11 divides 6237. 10864197531? 1-0+8-6+4-1+9-7+5-3+1=11 so 11 divides 10864197531. Favorite 13 divisibility rule, similar to 7: ABCD is divisible by 7 if ABC + 4D is divisible by 13. ex: 1664 --> 182 --> 26 = 2*13, 1664 is divisible by 13.

@maxbow-arrow5931 2 жыл бұрын

This 7/13 method actually works for all primes p, with the coefficient of D being equal to the multiplicative inverse of 10 mod p. Here's a quick proof: let our number be 10X+D, and A be such that 10A=1. Then 10(X+AD)=10X+D mod p, so X+AD is zero iff 10X+D is. For example, for 17, the rule is 'X-5D', and for 19 it's 'X+2D'

@henrymarkson3758 3 жыл бұрын

That's damn smart! Never a dull moment on your channel

@vedantneharkar6695 5 ай бұрын

Why does factorisation of the number give that one numeral out of all factors?

@thebruhtruth8973 3 жыл бұрын

Awesome as usual😁😁

@Qermaq 3 жыл бұрын

For numbers between 3 and 5 digits, here's how I test divisibility by 7. Divide the number to become 100a+b. Then find 2a+b. 2a+b will be the same as 100a + b in terms of congruence to mod(7). You need to know your 7s up to 100, and depending on your brain 5 digits might be too many or as many as 6 or more is ok. Same works for 11, but just find a+b. Reason it works is that we're finding a multiple of n that's really close to 100. So for 7 we're really just subtracting 98a which is a multiple of 7. The mod(n) to which our number is congruent will not change by adding/subtracting any integer zn.

@italixgaming915 3 жыл бұрын

When you need to test if a number can be divided by 7, 11 or 13, you can do all of that at once using 1001=7.11.13. In our example you have 6869=6.1001+863 then if 6869 can be divided by 7, 11 or 13 so does 863. And here we see that this doesn't work. This is obvious for 11 (8+3=11, not 6 or 17), for 7 you can write 863=840+23 and for 13 you have 863=850+13. Here are the other things you can in order to prove that 6869 is a prime number. For 2, 3 or 5, it's quite obvious. I just did 7, 11 and 13. So now I need to test 17 and I see that 6869=6800+69 so I can eliminate both 17 and 23. After that I use 3.37=111 and I write: 6869=6660+209=180.37+11.19 and I can eliminate both 19 and 37. After that I use 29.31=899 and I write : 6869=5970+899 but 5970=30.199 so I can eliminate both 29 and 31. For 41 and 43 I use the same method: 6869=6150+759 but 759=3.11.23 6869=6450+459 but 459=9.51 For 47 and 53 I use 47.53=2491 that I add to my number: I obtain 9360=9.1040=9.40.26 so I can eliminate 47 and 53. For 59 and 61 same idea I use 59.61=3599 that I withdraw: I obtain 3270=30.109 so I can eliminate 59 and 61. For 67 and 73 I use 67.73=4891 that I add: I obtain 11760=10.(1200-24)=10.12.98 so I can eliminate 67 and 73. For 71 the other factor would be a prime number that ends by 9 and be lower than 100 but the bigger prime number with that property, which is 89, is too small. Same for 79, I would need a prime number that ends by 1 and there aren't any between 71 and 101.

@logannathan.p9542 2 жыл бұрын

What is largest prime number now? M51??

@Qermaq 2 жыл бұрын

@@logannathan.p9542 That's classified, man. ;)

@logannathan.p9542 2 жыл бұрын

@@Qermaq then M51?

@dlevi67 3 жыл бұрын

Liked - because of the Pascal triangle and powers of 11! Pretty obvious (as others have commented), but nice.

@logannathan.p9542 2 жыл бұрын

What is largest prime number now? M51??

@armacham 3 жыл бұрын

Not to be nitpicky, but shouldn't you be testing p

@robertcitrus5974 3 жыл бұрын

But n is even, so there’s no need. If n were odd then yes

@tonyhaddad1394 3 жыл бұрын

@@robertcitrus5974 n is odd

@Deathranger999 2 жыл бұрын

You don’t need to here because 83^2 is only slightly bigger, so we know sqrt(6869) is not an integer.

@cH3rtzb3rg 2 жыл бұрын

You can also argue that since 80² < n < 83² and there are no primes between 80 and 83, you only need to check until 79.

@renangomes5880 3 жыл бұрын

Awesome!

@oenrn 3 жыл бұрын

I did it by brute force: ‐ it can be divided by 2 twice (easy to do in your head) - then the next prime that divides it is 73 (used a calculator for this, yes), which divides it twice - no other factors up to 83, then it's easy to see anything above 83 is not possible as 83 squared > 6869, so 6869 itself must be prime

@cH3rtzb3rg 2 жыл бұрын

You can test-divide by any number which is not a multiple of 2 or 5 by starting from the last digit. E.g. try to divide 36604901 by 17: If it is divisible the last digit of the result must be 3, subtract 3*17=51, drop last 0: 3660485, that means the next digit needs to be 5, subtract 5*17=85, drop last 0: 366040, next digit is 0 subtract 0*17=00, drop last 0: 36604, next digit is 2 subtract 2*17=34, drop last 0: 3657, next digit is 1 subtract 1*17=17, drop last 0: 364, next digit is 2 subtract 2*17=34, drop last 0: 33 -- not a multiple of 17 --> number was not divisible by 17. If you check 73: 36604901 last digit must be 7 subtract 7*73=511, drop last 0: 3660439, next digit is 3 subtract 3*73=219, drop last 0: 366022, next digit is 4 subtract 4*73=292, drop last 0: 36573, next digit is 1 subtract 1*73=073, drop last 0: 3650, next digit is 0 subtract 0*73=000, drop last 0: 365, which is 5*73 Therefore 36604901 = 73*501437