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

5
votes
1answer
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$ ...
1
vote
2answers
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 ...
12
votes
3answers
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. ...
6
votes
1answer
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 ...
0
votes
0answers
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,...
3
votes
3answers
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 ...
13
votes
3answers
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 ...
4
votes
1answer
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 ...
1
vote
2answers
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 ...
2
votes
1answer
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?
2
votes
1answer
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
3
votes
1answer
39 views

Solving $(ap)^2-d(bq)^2=1$ for distinct primes $p,q$

I'm pondering the following claim regarding special cases of the Pell equation. Conjecture: For every pair of distinct primes $p$ and $q$, there exist integers $a$ and $b$, and a non-square integer $...
1
vote
1answer
38 views

Number theory, prove that a prime number $p \mid 1$

Consider a prime number $p > 1$ and $a \in \mathbb{Z}$ and $p < a$. We know $p \mid a$, then $a = p.b$ for $b \in \mathbb{N}$. We also already know the congruence $a \equiv 1 (\text{mod } m)$ ...
0
votes
0answers
34 views

Is it possible to count primes using a regression model?

Let $Y$ equal the number of primes less than a value $X$. Given the equation: $Y =Ax^B + C$ Where $A$ is a regression coefficient, $B$ is some exponent and $C$ is an error term, can one estimate ...
0
votes
1answer
19 views

Find a unique value for $d$ in $(d \cdot e) \pmod{F} \equiv 1$

Given that I know the value of $e$ and $F$. How to determine an unique integer value for $d$ in such a way that the reminder of the division of $(d \cdot e)$ per $F$ is equal to one? $(d \cdot e) \...
1
vote
1answer
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 ...
3
votes
1answer
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. ...
5
votes
1answer
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 ...
5
votes
4answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
31 views

Help understanding one of Euler's theorem in Number Theory [duplicate]

I am looking at two Euler's theorems in my textbook which are the following: If $p$ is prime and $a$ is any whole number, then $(a+1)^p - (a^p + 1) $ is evenly divisible by $p$. If $p$ is prime and $...
1
vote
5answers
53 views

Then there exists a unique natural number $b$ less than $p$ such that $ab \equiv 1 \pmod{p}$. [duplicate]

Full question: Let $p$ be a prime and let $a$ be an integer such that $1 \leq a < p$. Then there exists a unique natural number $b$ less than $p$ such that $ab \equiv 1 \pmod{p}$. Looking for the ...
2
votes
0answers
44 views

simplifying a sum with modular arithmetic

Let $p\!\geq\!3$ be a prime and $n\!\in\!\mathbb{N}$. For $i\!=\!1,\ldots,n$ let $w_i\!=\!2i\!-\!n\!-\!1$. Let $n\%p$ denote the remainder in the integer division of $n$ by $p$. Can the following sum ...
-1
votes
2answers
82 views

Is this definition of Mersenne Primes correct? [closed]

According to my understanding, the definition of Mersenne Prime is the following: A Mersenne Prime is a prime number that is obtained by using the formula $2^n-1$, where $n\in\mathbb{N}_+$
1
vote
1answer
37 views

Fermat's little theorem's proof for a negative integer

I'm in the process of proving Fermat's little theorem. For a prime integers $p$ we have $a^p \equiv a \mod{p}$ I proved it for a non-negative $a$, not I need to generalize the case to an ...
2
votes
1answer
26 views

proof of condition of irrationality

I want to find a proof of the fact that $a^b$ is irrational if $a$ is a prime and $b$ is not an integer. Motivation behind this question: I was posed a question , of finding what is the probability of ...
2
votes
1answer
90 views

Prove that $\prod\limits_{2 < p \leq y}\left(1-\frac{2}{p}\right)\sim\frac{D}{\log ^2 y}$ [duplicate]

I'm writing my bachelor thesis about Brun's sieve method and his theorem. In one proof I found this statement without further explanation. It is important to show that the product doesn't converge "...
1
vote
1answer
45 views

Prime conjecture containing primorial

Help me find the exact conjecture statement. What I roughly remember is that it stated that the difference between primorial $n\#$ (product of first $n$ primes) and "some" larger number than the ...
1
vote
0answers
25 views

Numbers that equal the product of their digits with a constant

I've received recently a problem from my friend (and I really find it a hard one), it's about numbers that equal the product of their digits with a constant. Well, to make it clear: Let $m \in\mathbb ...
2
votes
0answers
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 ...
0
votes
1answer
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 ...
7
votes
1answer
152 views

Why can this cosine sum function show all primes less than $N^2$?

I constructed this cosine sum that puts all primes within N on line y=1, and its zeros show the sieve by primes less than N. For $x<N^2$, they are all primes. $$ P(N,x)=\sum_{n=2}^{N}\frac{1}{n}\...
0
votes
0answers
25 views

Is this algorithm for testing whether or not an integer is prime correct?

Suppose I want to determine whether or not integer $p$ is prime. I create a cycle graph with $p$ vertices ($C_p$). I take the edge-complement of this graph, which will be the complete graph ($K_p$) ...
0
votes
2answers
44 views

Find two pairs of relatively prime positive integers $(a,c)$ so that $a^2+5929=c^2$. Can you find additional pairs with $gcd(a,c)>1$?

This question was asked before, but I was wondering if there's a different approach for this problem. Find two pairs of relatively prime positive integers $(a,c)$ so that $a^2+5929=c^2$. Can you find ...
0
votes
0answers
25 views

Is there a constant $C$ such that $\prod_{p\leq x}\dfrac{p-1}{p}<\dfrac{e^{-\gamma}}{\log x}\cdot C$?

By Mertens' third theorem: $$\prod_{p\leq x}\dfrac{p-1}{p}\sim\dfrac{e^{-\gamma}}{\log x}$$ But does there exist a constant $C$ such that: $$\prod_{p\leq x}\dfrac{p-1}{p}<\dfrac{e^{-\gamma}}{\log x}...
1
vote
1answer
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" ...
1
vote
0answers
35 views

Lower bound on $\prod_{p|n}\left(1-\frac{1}{p^2}\right)$

I am wondering if a lower bound for $\prod_{p|n}\left(1-\frac{1}{p^2}\right)$ exists, where p is a prime. My first instinct was to make this step (As one usually does for this kind of question) $...
1
vote
0answers
20 views

units of the quotient ring of the integers over a prime power $[{\Bbb Z}/P^e\Bbb Z]^*$ is cyclic multiplicative group

I am studying Algebra as an extra curricular research project and in the reading I was assigned, the author somewhat offhandedly mentions that the units of ${\Bbb Z}/P^e\Bbb Z$, which is to say $$({\...
1
vote
0answers
54 views

Convergence of the Euler product

Suppose that the Riemann Hypothesis is true. It is well known that then the Dirichlet series $$\sum_{n=1}^\infty\frac{\mu(n)}{n^s}$$ converges in the half-plane ${\rm {Re}}\, s>\frac{1}{2}$. Does ...
0
votes
0answers
50 views

Concatenating the first n semiprimes (in order) to get a semiprime $469101415$…

The concatenation of the first $1,2,3,6,43$, and $61$ semiprimes (in order) is a semiprime (!), $4=2 . 2$ $46=2 . 23$ $469=7 . 67$ $469101415=5 . 93820283$ $4691014152122....121122123129$ (proven ...
2
votes
1answer
62 views

Are primes less than the sum of divisors?

I am trying to prove that Let $p_n$ be the $n$th prime number, $\sigma (n)=\sum_{d|n}d$. Prove that $$\sigma(n) \le p_n$$ It seems obvious at first glance-to me, at least the sum of divisors of ...
0
votes
0answers
52 views

Are all the numbers in this sequence a prime number?Sequence : $31 , 331, 3331, 33331$ [duplicate]

The given sequence is : $31,331,3331,33331....$ where the $n^{th}$ number has n $3$'s followed by a $1$. The question asked is to find are all the numbers prime? If not all how many terms from start ...
1
vote
0answers
23 views

Find all functions such that $f(m)+f(n)|m^p+n^p$

For fixed prime number $p$, find all $f:\mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ such that $f(m)+f(n)\mid m^p+n^p$ for all $m,n\in \mathbb{Z}^+$ I managed to get only that for prime $q$ we have $f(q)=q^...
1
vote
0answers
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.
1
vote
2answers
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) ...
3
votes
3answers
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 ...
2
votes
1answer
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? ...
0
votes
1answer
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 ...
0
votes
3answers
50 views

How many numbers less than 100 have the sum of factors as odd?

How many numbers less than 100 have the sum of factors as odd? Answer is 16 This question and explanation is taken from careerbless.com The link given derives the answer using some properties ...
0
votes
1answer
77 views

There are infinitely many primes congruent to 9 mod 10

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