Determine (with proof) the set of all prime numbers

In summary, the pattern of the numbers is that the first number is always double the second number minus one. The third number is always the sum of the first two numbers. The fourth number is always double the third number minus one. And so on, with each subsequent number being the sum
  • #1
750
199
Homework Statement
Determine (with proof) the set of all prime numbers that can divide two successive integers of the form ## n^{2}+3 ##.
Relevant Equations
None.
Proof:

Let ## p ## be the prime divisor of two successive integers ## n^{2}+3 ## and ## (n+1)^{2}+3 ##.
Then ## p\mid [(n+1)^{2}+3-(n^{2}+3)]\implies p\mid (2n+1) ##.
Observe that ## p\mid (n^{2}+3) ## and ## p\mid (2n+1) ##.
Now we see that ## p\mid [(n^{2}+3)-3(2n+1)]\implies p\mid (n^{2}-6n)\implies p\mid [n(n-6)] ##.
Since ## p\nmid n ##, it follows that ## p\mid (n-6) ##.
By Euclidean Algorithm, we have that ## p\mid (2n+1)\implies p\mid [2(n-6)+13] ##.
Therefore, the set of all prime numbers that can divide two successive integers of the form ## n^{2}+3 ## is ## {13} ##.
 
Physics news on Phys.org
  • #2
Math100 said:
Homework Statement:: Determine (with proof) the set of all prime numbers that can divide two successive integers of the form ## n^{2}+3 ##.
Relevant Equations:: None.

Proof:

Let ## p ## be the prime divisor of two successive integers ## n^{2}+3 ## and ## (n+1)^{2}+3 ##.
Then ## p\mid [(n+1)^{2}+3-(n^{2}+3)]\implies p\mid (2n+1) ##.
Observe that ## p\mid (n^{2}+3) ## and ## p\mid (2n+1) ##.
Now we see that ## p\mid [(n^{2}+3)-3(2n+1)]\implies p\mid (n^{2}-6n)\implies p\mid [n(n-6)] ##.
Since ## p\nmid n ##, it follows that ## p\mid (n-6) ##.
Why is ##p\mid n## impossible? If ##p|n## then ##p|((n^2+3) -n\cdot n)## and thus ##p=3.## However, if ##3|n## then ##3\nmid (n^2+2n+4)=((n+1)^2+3).##

Now, I see that ##p\nmid n.##
Math100 said:
By Euclidean Algorithm, we have that ## p\mid (2n+1)\implies p\mid [2(n-6)+13] ##.
Wait again. We know ##p|(2n+1)## and ##p|(n-6)##. So ##p|((2n+1)-2\cdot (n-6))=13,## i.e. ##p=13.##
Math100 said:
Therefore, the set of all prime numbers that can divide two successive integers of the form ## n^{2}+3 ## is ## {13} ##.
Yes, that is right.

It wasn't asked for, but is there an example of such an ##n##?
 
  • Like
Likes Math100
  • #3
fresh_42 said:
Why is ##p\mid n## impossible? If ##p|n## then ##p|((n^2+3) -n\cdot n)## and thus ##p=3.## However, if ##3|n## then ##3\nmid (n^2+2n+4)=((n+1)^2+3).##

Now, I see that ##p\nmid n.##

Wait again. We know ##p|(2n+1)## and ##p|(n-6)##. So ##p|((2n+1)-2\cdot (n-6))=13,## i.e. ##p=13.##

Yes, that is right.

It wasn't asked for, but is there an example of such an ##n##?
Should I include/add why ## p\nmid n ## in this proof just like how you did it above? And an example of such an ## n ## is ## 6 ##.
 
  • Like
Likes fresh_42
  • #4
Math100 said:
Should I include/add why ## p\nmid n ## in this proof just like how you did it above? And an example of such an ## n ## is ## 6 ##.
I'd say yes because it is (at least to me) not obvious. You could as well start with the exclusion of ##p=3## in which case ##p\nmid n## becomes obvious from ##p|(n^2+3).##

Here are some more ...

1​
4​
0,3076923077​
2​
7​
0,5384615385​
3​
12​
0,9230769231​
4​
19​
1,4615384615​
5​
28​
2,1538461538​
6​
39​
3​
7​
52​
4​
8​
67​
5,1538461538​
9​
84​
6,4615384615​
10​
103​
7,9230769231​
11​
124​
9,5384615385​
12​
147​
11,3076923077​
13​
172​
13,2307692308​
14​
199​
15,3076923077​
15​
228​
17,5384615385​
16​
259​
19,9230769231​
17​
292​
22,4615384615​
18​
327​
25,1538461538​
19​
364​
28​
20​
403​
31​
21​
444​
34,1538461538​
22​
487​
37,4615384615​
23​
532​
40,9230769231​
24​
579​
44,5384615385​
25​
628​
48,3076923077​
26​
679​
52,2307692308​
27​
732​
56,3076923077​
28​
787​
60,5384615385​
29​
844​
64,9230769231​
30​
903​
69,4615384615​
31​
964​
74,1538461538​
32​
1027​
79​
33​
1092​
84​
34​
1159​
89,1538461538​
35​
1228​
94,4615384615​
36​
1299​
99,9230769231​
37​
1372​
105,5384615385​
38​
1447​
111,3076923077​
39​
1524​
117,2307692308​
40​
1603​
123,3076923077​
41​
1684​
129,5384615385​
42​
1767​
135,9230769231​
43​
1852​
142,4615384615​
44​
1939​
149,1538461538​
45​
2028​
156​
46​
2119​
163​
47​
2212​
170,1538461538​
48​
2307​
177,4615384615​
49​
2404​
184,9230769231​
50​
2503​
192,5384615385​
 
  • Wow
Likes Math100

1. What is the definition of a prime number?

A prime number is a positive integer that is only divisible by 1 and itself. In other words, it has exactly two factors.

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

To determine if a number is prime, you can use a method called the Sieve of Eratosthenes. This involves creating a list of all numbers from 2 to the number in question, and then crossing out all multiples of each number. If a number is not crossed out, it is considered prime. Alternatively, you can also check if a number is divisible by any number between 2 and its square root.

3. What is the set of all prime numbers?

The set of all prime numbers is an infinite set, as there is no largest prime number. Some examples of prime numbers include 2, 3, 5, 7, 11, 13, 17, 19, 23, and so on.

4. How can you prove that a number is prime?

To prove that a number is prime, you can use a variety of methods such as the Sieve of Eratosthenes, the Fundamental Theorem of Arithmetic, or the Euclidean algorithm. These methods involve showing that the number has no factors other than 1 and itself.

5. Are there any patterns or rules for prime numbers?

There are many patterns and rules for prime numbers, but they are not consistent or predictable. One example is the "twin prime conjecture," which states that there are infinitely many pairs of prime numbers that differ by exactly 2, such as 41 and 43. However, this has not been proven to be true for all numbers and remains an open question in mathematics.

Suggested for: Determine (with proof) the set of all prime numbers

Back
Top