Testing Primality of 377 with Divisibility

  • Context: Undergrad 
  • Thread starter Thread starter rajeshmarndi
  • Start date Start date
  • Tags Tags
    Divisibility Testing
Click For Summary

Discussion Overview

The discussion revolves around testing the primality of the number 377 using various methods of divisibility. Participants explore different approaches to determine whether 377 is prime, including the use of multiplication series and the square root method, while also addressing the implications of their methods.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant suggests testing the divisibility of 377 using the product of odd numbers up to 125, arguing that if 377 is prime, it should not divide this product.
  • Another participant points out that testing factors only up to the square root of 377 (approximately 19.4) is sufficient, as any larger factor would have a corresponding smaller factor.
  • Some participants emphasize that 377 can be expressed as the product of 13 and 29, indicating it is not prime.
  • There is a contention regarding the logic of testing divisibility, with one participant arguing that testing whether 377 is a factor of a larger product does not provide conclusive evidence of its primality.
  • One participant mentions that they will only consider odd numbers in their multiplication series, excluding 2, and questions the relevance of including even numbers in the discussion.
  • Another participant raises a point about non-prime numbers being factors of the product series, suggesting that certain non-prime numbers may not appear in the product.

Areas of Agreement / Disagreement

Participants express differing views on the methods for testing primality, with some supporting the use of multiplication series and others advocating for the square root method. There is no consensus on the best approach, and the discussion remains unresolved regarding the implications of the various methods proposed.

Contextual Notes

Participants have not fully clarified the assumptions behind their methods, and there are unresolved questions about the practicality and effectiveness of the proposed approaches to testing primality.

rajeshmarndi
Messages
319
Reaction score
0
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.
 
Mathematics news on Phys.org
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.
 
mfb said:
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.

mfb said:
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.
 
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.
 
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
 
There is nothing special about 2.
rajeshmarndi said:
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=432 should be the first non-prime which is not a factor of this large product.
 
mfb said:
1849=432 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.
 

Similar threads

Undergrad Primality test from pascal triangle
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Math Myth: A prime is only divisible by 1 and itself
  • · Replies 4 ·
Replies
4
Views
2K
MHB Tests of Divisibility- Simple tricks
  • · Replies 11 ·
Replies
11
Views
6K
Graduate About a natural extension of Collatz conjecture
  • · Replies 3 ·
Replies
3
Views
1K
MHB -c5.LCM and Prime Factorization of A,B,C
  • · Replies 3 ·
Replies
3
Views
1K
Determine whether the integer 701 is prime by testing?
  • · Replies 1 ·
Replies
1
Views
3K
Graduate Sacks' Autistic Twins and Prime Testing
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Finding out which prime factors a integer is made up by
  • · Replies 9 ·
Replies
9
Views
3K
Graduate Why dividing zero by zero remains a problem
  • · Replies 28 ·
Replies
28
Views
5K
Undergrad Composite Number Test: Find Factors w/ Quadratic Equations
  • · Replies 6 ·
Replies
6
Views
2K