Prime numbers are natural numbers greater than 1 not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

learn more… | top users | synonyms

0
votes
0answers
18 views

Prove that the product of the primitive roots modulo the prime p is congruent to 1 modulo p if p > 3? [duplicate]

Prove that the product of the primitive roots modulo the prime p is congruent to 1 modulo p if p > 3. Just started going over primitive roots in class and a bit lost with this question. I do know ...
2
votes
1answer
58 views

Probability of prime numbers

Say we use the Euclidean construction for prime numbers and take a set $S$ solely containing prime numbers, so that $p_n$ is the greatest prime within S. What is the probability that $1+p_1 \cdots ...
4
votes
0answers
64 views

Is there a relationship between local prime gaps and cyclical graphs?

By defining the following algorithm I was able to generate some interesting graphs using the values of the gaps between consecutive primes: Start in any prime $p_i$, this will be the initial ...
21
votes
6answers
4k views

Understanding Euclid's proof that the number of primes is infinite. [duplicate]

In Euclid's proof, if $p_1, p_2, \dots, p_n$ are the only primes then $p_1 \times p_2 \times \dots \times p_n + 1$ is not divisible by any of $p_1, p_2, \dots, p_n$ (because of some algebraic facts), ...
2
votes
0answers
37 views

A very nice pattern involving prime factorization

A while ago I was fiddling around with prime numbers and C++. I defined: $$f_a(b)= \text{ the amount of numbers } 2^a\leq n<2^{a+1}\text{ with } b \text{ prime factors}$$ I calculated $f_a(b)$ for ...
0
votes
1answer
31 views

Show, using the rational root test, that $\sqrt{p}$ is irrational, for any positive prime $p$.

Show, using the rational root test, that $\sqrt{p}$ is irrational, for any positive prime $p$. The lecturer specifically asks that he wants us to show the above question, through showing that ...
3
votes
0answers
31 views

Recreational math dealing with twin primes

This is kinda recreational math with a goal in mind of progressing further toward a proof of the twin prime conjecture. Consider this: We start with a random prime: $109$ $3*109=327$ $327 ...
0
votes
2answers
49 views

Totien-Sum: why GCD( {n}/d, q/d) = 1; implies Sum{Totient(d/q) } = q

Have seen answer to this question. still don't understand.. Totient sum is defined: q = Sum(Totient (d) ); sum on all d : d|q More specific; The proof has these steps: 1. If d is a divider ...
0
votes
1answer
53 views

Primality testing though trial division.

I am having difficulty to understand this statement mentioned here: Remember that any composite integer n is build out of two or more primes n = P * P … P is largest when n has exactly two ...
3
votes
2answers
34 views

How can I prove that a linear recurrence $x_{n+1} = αx_n - β$ will contain a composite number in the sequence?

I'm working on a homework problem about finite automata and I got stuck trying to prove a fact about prime numbers that I think should be true. Given a prime $p$ and integers $α$ and $β$, can I show ...
0
votes
1answer
33 views

Find a prime $p>5$ such that $x^2 +1$ is reducible in $\mathbb Z_p[x]$

Find a prime $p>5$ such that $x^2 +1$ is reducible in $\mathbb Z_p[x]$. Can anyone please give me some hints as to how I can go about finding this value of $p$?
6
votes
1answer
46 views

Sum of the reciprocal of the prime-position primes.

The primes are $2, 3, 5, 7, 11, 13...$ The sum of the reciprocals of the primes diverges, proven by Euler: $$\sum_{n=1}^\infty{\frac{1}{p_n}}=\infty$$ Here, $p_n$ is the $n$-th prime. I'm asked to ...
1
vote
0answers
33 views

Compositeness test for Wagstaff numbers

Is this proof acceptable ? Definition Let $W_p=\frac{2^p+1}{3} $ with $p$ prime and $p>3$ . Theorem If $W_p$ is prime then $7^{\frac{W_p-1}{2}} \equiv -1 \pmod {W_p}$ Proof Let $W_p$ be a ...
0
votes
1answer
74 views

Primes Between Squares of Primes

Is this problem still open? I know that Henri Brocard conjectured that there are at least four primes in the interval between each pair of consecutive squares of primes from nine onward. ...
2
votes
2answers
95 views

Fibonacci Numbers and Legendre symbol

How to prove congruence below ? $$F_{p-\left( \frac{5}{p}\right)} \equiv 0 \pmod p$$ Where $\displaystyle \left( \frac{}{}\right)$ is legendre symbol, and $\displaystyle p$ is a prime number.
1
vote
2answers
50 views

How can I solve this using prime factors?

I'm stuck with this problem: $2^x \cdot 3^3 \cdot 26^y = 39^z$ for $x, y, z \in \mathbb{N}$. I know that there isn't a natural solution for the equation, but I need to "prove" it using prime factors. ...
2
votes
0answers
44 views

Prove, by giving an example , Fermat's Little Theorem

Prove, by giving an example, that, if n is not prime, a≠0(mod n) then it is not necessarily true that { [1]n,[2]n.........[n-1]n} = {[a.1]n,[a.2]n,.......[a.(n-1)]n} could you give me any hint to ...
6
votes
2answers
92 views

example, that Wilson's Theorem is not necessarily true

Show by an example, that Wilson's Theorem is not necessarily true if $p$ is not prime. (In fact, it is not hard to show that it is never true if $p$ is not prime, but I am not asking you to do that.) ...
0
votes
2answers
24 views

Calculating the difference of the factors of a semiprime

Let there be a semiprime $N=p q$ where $p$ and $q$ are prime numbers. If the value of $N$ is given, is there any way to calculate the value of $(p-q)$. If not exactly then approximately ? Update : ...
1
vote
1answer
58 views

Compositeness test for repunits

Is this proof acceptable ? Definition Let $R_p=\frac{10^p-1}{9} $ with $p$ prime be a repunit number . Theorem If $R_p$ is prime then $7^{\frac{R_p-1}{2}} \equiv -1 \pmod {R_p}$ Proof Let $R_p$ ...
1
vote
1answer
39 views

The Number of Two-digit Primes Which the Sum of their Digits is 6

Problem: Find the number of two-digit primes which the sum of their digits is six. We had this problem in a mathematic examination. The problem can be solved by testing all two-digit primes, but ...
0
votes
0answers
36 views

If $p=x^2+y^2$ is a prime number, then $\left( \frac{x+y}{p} \right) = \left( \frac{2}{x+y} \right) $

Let $p=x^2+y^2$ be a prime number. How to prove that $\left( \dfrac{x+y}{p} \right) = \left( \dfrac{2}{x+y} \right) $ (where $\left(\frac ab\right)$ denotes the Jacobi symbol)?
3
votes
1answer
48 views

An integer sequence defined by recursion

Let's define the following integer sequence. We start with $a_1=3$. Then we define $$a_{n+1}=a_{n}+(a_{n}\,\text{mod}\,p_n)$$ where $p_n$ is the greatest prime (strictly) less than $a_n$, and ...
5
votes
2answers
37 views

Exponential Power Series where Powers are Prime

I am looking for information in regards to a couple particular functions: 1) $P(x)=\sum_{p\in\mathbb{P}}\frac{x^p}{p!}$ 2) $Q(x)=\sum_{p\not\in\mathbb{P}}\frac{x^p}{p!}$ (assuming $0, 1$ are ...
-3
votes
1answer
58 views

Mersenne numbers fail primality test at 2047 itself. How could we believe Mersennes are primes?

M$_{11}=2047$ is a composite number. How could one, not check the primaility of such a small number and believe that all Mersenne numbers are primes?
1
vote
1answer
43 views

Finding an upperbound for $\sum_{i=2}^{n}\bigg(\prod_{k=2}^{i}\dfrac{p_k-2}{p_k}\bigg)$

I was wondering whether there exists a known upperbound for: $$f(n)=\sum_{i=2}^{n}\bigg(\prod_{k=2}^{i}\dfrac{p_k-2}{p_k}\bigg)$$ For example: ...
3
votes
0answers
72 views

How close are we to knowing the rate of convergence to $0$ of $\prod_{p\le x}(1-1/p)^{-1}-e^\gamma\log x $?

This is a question related to an earlier one of mine, which I may answer myself eventually, as I have learnt more about the topic. Despite what one can read on the MathWorld page about Mertens' third ...
0
votes
1answer
42 views

Finding the $18$th cyclotomic polynomial $\phi_{18}(X))$.

I know that for an $n$th cyclotomic polynomial $\phi_n(X)$ the following equations hold: $x^n-1=\prod_{n_1|n} \phi_{n_1}(X)$ For $n=p$ prime, $\phi_p(X)=X^{p-1}+...+X+1$ So I used the following ...
1
vote
2answers
148 views

Check if a number is Carmichael

I am trying to implement Modified Miller-Rabin Algorithm by Shyam Narayanan (https://math.mit.edu/research/highschool/primes/materials/2014/Narayanan.pdf). The algorithm demands to check if a number ...
1
vote
0answers
33 views

Is there a standard way of defining a total order between Gaussian primes?

In the case of $\Bbb N$ and $\Bbb Z$ the gap between two consecutive primes could be defined roughly speaking as the absolute value of the (1-dimensional) distance between those mentioned consecutive ...
15
votes
2answers
263 views

Primes of form $a^2 + 24b^2$

For a prime number $p \neq 2$, $3$, is it necessarily the case the prime number can be written in the form $a^2 + 24b^2$ if and only if $p \equiv 1 \text{ mod }24$? I think this has to be true based ...
8
votes
2answers
111 views

Is $every$ prime factor of $\frac{n^{163}-1}{n-1}$ either $163$ or $1\;\text{mod}\;163$?

This was inspired by this question. More generally, given prime $p$ and any integer $n>1$, define, $$F(n) = \frac{n^p-1}{n-1}=n^{p-1}+n^{p-2}+\dots+1$$ Q: Is every prime factor of $F(n)$ ...
5
votes
0answers
58 views

Largest prime known to ancients

As is well known, Fermat couldn't check the primality of $F_{5} = 2^{2^{5}} + 1$. This raises an interesting question : what was the largest prime number that was known to ancients (particularly ...
1
vote
1answer
45 views

$\ln(n)$ - Average Length of Prime Gaps

The natural logarithm of $n$ is a good approximation of the prime gap near $n$. On my calculator I enter this as $\ln(n)$. I have read from these pages: ...
2
votes
1answer
37 views

With which natural value of n, the polynomial will be prime value and why?

So. $P(n) = n^4 + n^2 + 1$ is a polynomial. I calculated that answer is 1. But I don't understand why?
1
vote
2answers
79 views

Reverse of Chinese Remainder Theorem

For the following: $(102n-51) \not\equiv 2 \pmod {2,3,5,7,11,13,...,\sqrt{102n-51}}$ (That's probably completely incorrect use of symbols, but I mean not equivalent to 2 mod any prime less than ...
13
votes
2answers
138 views

If $n$ is a positive integer, does $n^3-1$ always have a prime factor that's 1 more than a multiple of 3?

It appears to be true for all $n$ from 1 to 100. Can anyone help me find a proof or a counterexample? If it's true, my guess is that it follows from known classical results, but I'm having trouble ...
0
votes
4answers
48 views

How many numbers are possible from $a^x b^y c^z$?

How to calculate total nos of possible value made from given numbers. e.g. : $2^2 \cdot 3^1 \cdot 5^1$ . There $2$ , $3$ , $5$ , $2\cdot2$ , $2\cdot3$ , $2\cdot5$ , $3\cdot5$ , $2\cdot2\cdot3$ , ...
0
votes
1answer
16 views

Finding $n$ from the cumulative sum of the serie where $SUM(n) < \Pi < SUM(n+1)$

I have a serie of numbers: $$S = {1/1, 1/2, 1/3, 1/4, 1/5, 1/6, 1/7, 1/8, 1/9, 1/10, 1/20, 1/30, 1/40, 1/50, 1/60, 1/70, 1/80, 1/90, 1/100, 1/200, 1/300, 1/400, 1/500, 1/600, 1/700, 1/800, ...
1
vote
1answer
36 views

find $x$ given arbitrary $\pi(x)$

When seeking the nth prime, how would one determine (or approximate) $x$, given a $\pi(x)$ value? I've read that $x / log(x)$ is a decent approximation of primes below $x$, but nothing about the ...
1
vote
0answers
63 views

Probability that the discriminant of a quadratic field is divisible by a given prime number $p.$

Find the probability that the discriminant $D$ of a quadratic field $\mathbb{Q}(\sqrt{d})$ is divisible by a given prime number $p$ (beware: the result is not what you may expect.) This is an ...
3
votes
4answers
125 views

Who found the expression $n^2 - n + 41 $ for generating prime numbers?

I am doing some research and I cannot seem to find the answer anywhere so does anyone know who found the expression $n^2 - n + 41 $ for generating prime numbers?
3
votes
1answer
54 views

What would be the impact of a formula which explains the structure of primes?

Prime numbers are often defined as the most mysterious figures in mathematics and they have been being studied for almost 2500 years, yet we haven't fully understood what their nature and structure ...
2
votes
2answers
36 views

Limit of division vs Limit of subtraction

I was studying the Prime Number Theorem, which says $\lim_{x\to \infty} \frac{\prod(x)}{\frac{x}{\ln x}} = 1$, where $\prod(x) =$ number of primes $\leq x$. But the Wikipedia results for $\prod(x) - ...
1
vote
0answers
35 views

prime numbers - need a help

Helow, There is a question about prime numbers. Supposed that I already answer the first section. I try to answer the second section, but if n $\neq$ $2^{k}$ (for some k from the natural numbers, ...
1
vote
0answers
36 views

Relating prime numbers with irreducible polynomials using asymptotic density: is this a known theorem?

Let $p_m$ be the $m$th positive prime number in $\Bbb{Z}$. Then $f \in \Bbb{Z}[X]$ is irreducible if: $$ \liminf\limits_{m \to \infty} \dfrac{\# \{f(n) \text{ is prime } : n \lt p_m \}}{m} \gt 0 $$ ...
0
votes
1answer
57 views

Arithmetic Progressions with a Finite Number of Primes

Is there an arithmetic progression that includes {1} that also includes only a finite number of prime numbers? Or will all progressions including {1} have infinite primes?
1
vote
0answers
20 views

Determine the quadratic character of 293 mod 379…

Determine the quadratic character of 293 mod 379. Did several other problems like this with 3, 5, 60, -1 and 307 all mod 379 but still having a tough time with this problem. I can post up work from ...
5
votes
0answers
298 views

Is this proof of the twin prime conjecture? [closed]

Identifying twin primes [1] Any natural number $n : 1<n\leq p_x^2 $ where $n$ is not divisible by any prime number less than $p_x$ is a prime number, except when $n$ is one of those prime ...
1
vote
1answer
53 views

Can someone see the proof for that(number theory)

Please this is very important to me I would be so happy if someone is able to help... :) Let $I$ be a squarefree, natural and even number and $F$ the product of all primes $q$ where $(q-1) \mid I$. ...