Find its largest prime factor

#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.

[giuseppebassi]

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

[henrymarkson]

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

[Deathranger]

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.

[a_llama]

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

[Qermaq]

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

[theloganator]

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.

[dlevi]

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

[vedantneharkar]

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

[armacham]

Not to be nitpicky, but shouldn't you be testing p <= sqrtn? You wouldn't want to miss a situation where p is a perfect square of a single prime factor

[Qermaq]

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.

[sasharichter]

can you please state which math olympiad had this problem - it seems totally improbable that such a problem would be allowed...

[cHrtzbrg]

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

[Khalibi]

oh yes, why didn't i think of 11^4

[oenrn]

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

[linecheung]

I do the same thing until 2*6869*2*5329, but how can I know that 6869 is a prime number so easily.

[logannathan.p]

What is largest prime number now? M51??

[teeweezeven]

A lot of assumptions here. But very neat

[jarikosonen]

It looks like job for machine. But if its even larger number, then check by hand calculation?
Want to check about: 9007199254740881, prime or not?

[arrowrod]

CalculatorSoup 6869 1 billionth of a second to calculate.