# Tagged Questions

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.

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 ...
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. ...
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 ...
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.
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 ...
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.
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 ...
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 ...
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.
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. ...
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 ...
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 : ...
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 ...
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 ...
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 ...
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)?
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 ...
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?
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: ...
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 ...
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?
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)$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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?
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?
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 ...
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: ...
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$ , ...
16 views

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 ...
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 ...
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 ...