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

46 views

### Fractions of powers of primes.

I'm wondering whether the following statement is true: Let $p$ and $q$ be two prime numbers (or more generally let $p$ and $q\neq 0$ be integers with $\gcd(p,q)=1$). Then for all $\varepsilon >0$ ...
42 views

### Sum of reciprocals of prime-index-primes

Let $p_1=2$, $p_2=3$, $p_3=5$, $\ldots$ be an enumeration the prime numbers. If $q$ is a prime number, we call $p_q$ a prime-index-prime. A list of prime-index-primes can be found here. My question ...
147 views

### Why is the Fundamental Theorem of Arithmetic so important?

I've recently read about the Fundamental Theorem of Arithmetic and I think that I have just about understood the proof. What I found quite interesting at first was the "Fundamental" part in the name. ...
60 views

### Can we find prime numbers with any sum of digits (except those divisible by three)

I guess that this question is not something new and that there must be people who wanted to know if this question has an affirmative answer, but I would like to share it with you, because I really do ...
36 views

### For a prime p and a positive integer n

we define $A_{p,n} = \{(x,r) : 1 \leq x \leq n \textrm{, r is a positive integer, } p^{r} \textrm{divides x} \}$. Describe the set $A_{p,n}$ for p=5 , n=100. Does the set comprise of (5,1),(10,1),(15,...
49 views

### Does the PNT establish a connection between primes and the logarithm?

The prime number theorem states that $$\pi(x) \sim \frac x {\ln(x)}$$ Morally, this seems to suggest that there is a fundamental connection between primes and the natural logarithm. But since we're ...
725 views

### Can second degree polynomials generate as many as we wish prime numbers in the way described?

While I was getting in my pyjamas, a few minutes ago, the Euler polynomial $n^2+n+41$ came into my mind. As you know, this polynomial is famous because the set $\{f(0),f(1),...f(39)\}$ consists of ...
53 views

### How can I find the $n^{th}$ 'reversible prime'?

I just thought of an interesting problem when discussing prime numbers with a friend. Some numbers are prime, but even fewer numbers preserve their primality when we reverse their digits. So for ...
67 views

### Without calculating them determine whether $36^2+1$ and $154^2+1$ are prime and find the prime factors if not prime

I know that $36^2 + 1$ is prime, $154^2 + 1$ is not, both are equal to $1 \bmod 4$. The prime divisors of $154^2 + 1$ should also be of the form $1 \bmod 4$. Tried showing this by Wilson's theorem ...
35 views

### Is it always true, for a prime $p$, a generator $g$ of $\mathbb{Z}^*_p$ cannot be a quadratic residue modulo $p$?

Let $p$ be a prime, then is it true that a generator $g$ of $\mathbb{Z}^*_p$ cannot be a quadratic residue modulo $p$? And if yes why?
29 views

### Half primes in the set [closed]

Let S be 30 element subset of {1,2,....2015} such that every pair of elements in S are relatively prime. Prove that at least half of the elements in S are prime numbers
39 views

67 views

### Factoring semiprimes cost estimation

I have two problems that are the following. The first problem is the following: I need to estimate the cost of factorizing a given semiprime based on previous estimations. For example I have the time ...
53 views

### If $p_n$ is the $n^{th}$ prime, is it ever appropriate to speak of $p_{\aleph_0}$?

If $p_n$ is the $n^{th}$ prime, is it ever appropriate to speak of $p_{\aleph_0}$? I'm no math student. Your pardon if this is just some clearly obvious and easy answer, I'm just not seeing it. ...
57 views

### Would such a function be of any importance (primality test)?

While experimenting with some Maths, I came up with a really cool function. Let's call this function $\space \beta \space$. Which is a function of a real variable $\space r \space$. Here is the ...
61 views

### Total number of integers relatively prime to $p^2$

I am reading my number theory textbook and it states without proof that the total number of elements relatively prime to $p^2$ for some prime $p$ is $p(p-1)$. Why is this so? I know that the number of ...
26 views

### Calculate Euler inverse function

Given $n$ find all values n such that: $\phi(n) = 26$. I've searched over the web and I've managed to find the lower and upper bounds for n, but i don't know how to go on from this point. I'll be ...
31 views

36 views

### constructing primes without primality test [duplicate]

I am looking for ways to construct a prime without resorting to primality test. That can be an algorithm which would generate a prime from an arbitrary number or some defined set of inputs. For ...
18 views

### Can the extended euclidean algorithm be used to calculate a multiplicative inverse in this case?

$e = 503456131$ is a prime number. It is relatively prime to the number $b = 10000123400257488$ If I use the extended euclidean algorithm (using this python implementation) to calculate the ...
152 views

22 views

### Second degree polynomials in one variable (with integer coefficients) and limiting behavior of the number of prime values they take

As far as I know, we still do not have a proof that some second degree polynomial in one variable with integer coefficients takes an infinite number of prime numbers as its values, even the "simplest" ...
35 views

32 views

### Infinitely many primes of the form $16n+1$? [duplicate]

As the title states I need to prove there are infinitely primes of the form $16n+1$ but I have absolutely no idea how to do it.
54 views

### Proving the set of prime numbers in $\mathbb{Z+}$ is infinite

I'm trying to prove that for any $N \in \mathbb{Z^+}$, there exists only finite many integers $n$ with $\varphi(n) = N$ (i.e. finite amount of numbers that have $N$ numbers relatively prime to them) ...
44 views

### Density of primes containing specific digits

I suspect that primes containing certain digits (e.g. $1$, $3$) are way more common than primes containing other digits e.g. containing $2,4$ since my intuition tells me the latter combination is ...
29 views

### Why are primes of the form p^2 - 2 for prime p seemingly unusually likely to be factors of prime-exponent Mersenne numbers?

The sequence A049002 (primes of form $q^2 - 2$, where $q$ is prime) appears to contain a high proportion of elements that are factors of prime-exponent Mersenne numbers (see below). I wonder why? ...
14 views

### Modular Exponentiation doesn't work on a prime mod?

For 83627264^275372 mod 277 using modular exponentiation, I noticed that things weren't lining up when I checked them on Wolfram. So far I have this: 83627264^1 mod 277 = 133 83627264^2 mod 277 = 238 ...
I want to show that there are infinitely many primes $p$ such that $p = 9 \pmod {10}$. First, I can see that 19 is one of them. Assume there are finitely many, i.e., 19, $p_1, p_2 , \cdots , p_k$. ...