Testing Primality of 377 with Divisibility

In summary: So, in summary, by testing the divisibility of a number with a series of numbers up to its square root, we can determine if it is prime or not. This method may not be practical for very large numbers, but it is theoretically possible. Additionally, we can stop testing the divisibility at the square root of the number, as any factors larger than that would have a corresponding factor smaller than the square root. This method only works for odd numbers, as even numbers can be divided by 2.
  • #1
rajeshmarndi
319
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
  • #2
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.
 
  • #3
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.
 
  • #4
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.
 
  • #5
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
 
  • #6
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.
 
  • #7
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.
 
  • #8
Exactly.
 

1. How do you determine if a number is prime?

The most common way to determine if a number is prime is to check if it is divisible by any number other than 1 and itself. If it is not divisible by any other number, then it is considered a prime number.

2. What is the significance of 377 when testing for primality?

377 is a randomly chosen number that can be used to demonstrate the process of testing for primality. It is not a particularly special number in terms of prime numbers.

3. How do you use divisibility to determine if 377 is prime?

To test if 377 is prime, we would divide it by all numbers from 2 to its square root (19.4). If it is not divisible by any of these numbers, then it is considered prime. In this case, 377 is not divisible by any numbers from 2 to 19, so it is a prime number.

4. What is the time complexity of testing for primality using divisibility?

The time complexity for testing for primality using divisibility is O(√n), where n is the number being tested. This means that the time it takes to determine if a number is prime increases as the square root of the number increases.

5. Are there other methods for testing primality besides using divisibility?

Yes, there are several other methods for testing primality, such as the Sieve of Eratosthenes, the Miller-Rabin primality test, and the AKS primality test. These methods may be more efficient for larger numbers, but the divisibility method is a simple and straightforward approach for smaller numbers.

Similar threads

I Math Myth: A prime is only divisible by 1 and itself
    • General Math
Replies
4
Views
928
MHB -c5.LCM and Prime Factorization of A,B,C
    • General Math
Replies
3
Views
554
Determine whether the integer 701 is prime by testing?
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
MHB Tests of Divisibility- Simple tricks
    • General Math
Replies
11
Views
5K
MHB How to find whether a given number is prime or not?
    • General Math
Replies
1
Views
2K
B Intermediate Value Theorem and Synthetic Division
    • General Math
Replies
4
Views
1K
I Mutually disjoint sets of all integer powers?
    • General Math
Replies
2
Views
991
Finding out which prime factors a integer is made up by
    • General Math
Replies
9
Views
2K
MHB What is the remainder when $3^{2002}+7^{2002}+2002$ is divided by 29?
    • General Math
Replies
8
Views
6K
Why dividing zero by zero remains a problem
    • General Math
Replies
28
Views
4K

Hot Threads

Recent Insights

Back
Top