Undergrad Testing Primality of 377 with Divisibility

[rajeshmarndi]

Take for example 377 to test its primality. I will only test its divisibility with

(3*5*7*...*125) (because 377/3=125.67, so here the multiplication series end with 125 ).

377 will be able to divide it. (Since I know 377=13*29, i.e in the numerator 13 & 29 will be divided by 377, hence the total is divisible by 377.)

If a number is a prime, then the above method will not be divisible.

I am aware for very very big number, the multiplication series product will be enormously large. But isn't it, theoritically, it will work? Thanks.

 

[mfb]

You can stop testing possible factors at $\sqrt{377} \approx 19.4$. If there is a factor $a$ larger than 19.4, then there is also a factor $b=377/a$ smaller than 19.4.

Theoretically you can test the primality of every number that way, yes. It gets impractical and there are faster ways, but it is possible.

 

[rajeshmarndi]

You can stop testing possible factors at $\sqrt{377} \approx 19.4$. If there is a factor $a$ larger than 19.4, then there is also a factor $b=377/a$ smaller than 19.4.

(3*5*...*19). 377 won't divide this. Because 377=13*29. Since it has no 29. 377 won't be able to divide it.

Theoretically you can test the primality of every number that way, yes. It gets impractical and there are faster ways, but it is possible.

Yes.

 

[mfb]

Huh? You are reversing the logic.

You test if 377 is divisible by 2, 3, 5, ... up to 19.

You can also test of 377 is a factor of 2*3*5*7*...*125 but that doesn't tell you anything.
377 is a factor of that product. It is not a prime.
4 is not a factor of that product. It is not a prime either.

 

[rajeshmarndi]

I didn't get that.

For prime I will be only considering odd numbers. So I will not be taking 2 in the multiplication series.

(3*5*7*...*125) are not divisible by 373 and 379. Since they are prime. Also 125 is a large number to multiply in the series. If we knew a number is not divisible by 3,5 and 7. The multiplication can be reduced to (3*5*7*...*53), since 379/7=54.14

 

[mfb]

There is nothing special about 2.

I didn't get that.

Which part is unclear?

3*5*7*9*...*125 will have all non-prime numbers up to some large value as factor. So what?
1849=43² should be the first non-prime which is not a factor of this large product.

 

[rajeshmarndi]

1849=43² should be the first non-prime which is not a factor of this large product.

Ok, that's right. Because the product series has only one 43.

 

[mfb]

Exactly.