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

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 ...
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. ...
6
votes
1answer
44 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
votes
0answers
20 views

Proof their are infinitely many primes of the for 6n+5 [duplicate]

how would i go about proving that there are infinitely many primes of the form $$6n+5$$ any help would be appreciated.
1
vote
2answers
136 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 ...
2
votes
2answers
91 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
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
57 views

$2^k+3$ : Primality Brute Forcing Theory Below The Square Root

I'm testing a theory of brute forcing $2^k+3$. I've tried to test $(2^k)+3$ where $k=84$ but my computer just takes too long... Java takes too long too.. It's pretty stupid to assume 83 tests makes ...
0
votes
2answers
43 views

Representations of some primes as $3x^2-4y^2$?

I am looking for (elementary) proofs (idea of the proofs is also OK) or references to proofs of the followings: $$ p\equiv11\pmod{12}\longrightarrow p=3x^2-4y^2 $$ Any help appreciated.
0
votes
1answer
54 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. ...
10
votes
3answers
205 views

What is the most efficient algorithm for factorisation when an approximate value of one factor is known

If I am given the following number: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350 692006139 And am told that one of ...
0
votes
2answers
21 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 : ...
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 ...
1
vote
1answer
36 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 ...
5
votes
2answers
36 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 ...
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
47 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 ...
-3
votes
1answer
57 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: ...
2
votes
0answers
107 views

$f(x)\sim 1/x \implies (1+f(x))^x\to e$, but what family of functions maximizes the speed of convergence from below?

This problem is subordinate to finding out if $$\left(1+\frac{\log p_{n+1}}{p_n}\right)^{p_{n+1}/\log p_n},$$where $p_n$ is the $n$-th prime, never stabilizes above or below its limiting value, which ...
11
votes
1answer
676 views

The largest possible prime gap?

What is the largest possible prime gap if we observe only 1000-digits numbers? There are few conjectures about this question but is there something that we can say and be absolutely sure of it?
8
votes
2answers
110 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)$ ...
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
0answers
31 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 ...
0
votes
2answers
73 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 ...
-1
votes
0answers
38 views

Dream Function For Finding the Next Prime Following $n$

Is there any standard notation for this function, or is there not because it doesn't exist? If so, what is it? If not, let $D(n)$ be the dream function for finding the distance to the next prime ...
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 ...
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
43 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?
54
votes
4answers
3k views

Does the string of prime numbers contain all natural numbers?

Does the string of prime numbers $$2357111317\ldots$$ contain every natural number as its sub-string?
13
votes
2answers
134 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 ...
7
votes
4answers
19k views

Find the largest prime factor

I just "solved" the third Project Euler problem: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? With this on Mathematica: ...
0
votes
4answers
47 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
35 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 ...
3
votes
4answers
122 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
53 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 ...
3
votes
0answers
101 views

Legendre symbol identity: $\sum_{a=1}^{p-1}a \cdot \left (\frac{a}{p} \right)$ and $\sum_{a=1}^{p-1}2^a \cdot \left (\frac{a}{p} \right)$

I try to solve the following problems ($p$ is an odd prime) Find the sum $$\sum_{a=1}^{p-1}a \cdot \left (\frac{a}{p} \right)$$ Find the sum $$\sum_{a=1}^{p-1} 2^a \cdot \left (\frac{a}{p} \right)$$ ...
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, ...
5
votes
0answers
280 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
0answers
34 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 $$ ...
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 ...
0
votes
1answer
55 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
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$. ...
21
votes
2answers
709 views

Riemann's zeta as a continued fraction over prime numbers.

Riemann's zeta function is a function with many faces, I mean representations. I recently derived this one, bellow, as a continued fraction over prime numbers. $$ \zeta(s)=1 ...
5
votes
1answer
67 views

Combinations of four consecutive primes in the form $10n+1,10n+3,10n+7,10n+9$

Here $n$ is some natural number. For example, among the primes $< 1000$ I found four such combinations: \begin{array}( 11 & 13 & 17 & 19 \\ 101 & 103 & 107 & 109 \\ 191 ...
22
votes
1answer
640 views

One of any consecutive integers is coprime to the rest

After reading this question, I conjectured a generalization of it. Conjecture: Fix $k\in \mathbb N$. Then, for all $n\in \mathbb N$, one of $n+1,\ldots,n+k$ is coprime to the rest. I ...
1
vote
3answers
132 views

Which prime numbers is this inequality true for?

Inequality What values of $n$ satisfy the following inequality? $$2(n-2) < p_n\prod_{i=3}^n \left(\frac{p_i-1}{p_i}\right)$$ Where $p$ are prime numbers and the notation $p_i$ indicates the ...