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

-2
votes
0answers
23 views

Connection between prime numbers and transcendental numbers

I think there may be a strong connection between prime numbers and transcendental numbers. I am unable to prove what I have in mind by myself, so I am seeking help. My hypothetic theorem would be: ...
17
votes
0answers
78 views

Is there prime number of the form $0^1+1^2+2^3+3^4+4^5+…+(n-2)^{n-1}+(n-1)^n$?

Let A(n)= $0^1+1^2+2^3+3^4$....+$(n-2)^{n-1}+(n-1)^n$. So: A($1$)= $0^1$ A($2$)= $0^1+1^2$ A($3$)= $0^1+1^2+2^3$ A($4$)= $0^1+1^2+2^3+3^4$ and so on.... Is there prime number of such form?, ...
-5
votes
0answers
40 views

Anyone can help me solve the big mathematics problem? [on hold]

Any one can find the roots : With any positive integers n, have one positive integers m greater than n: $m \neq 6xy+x+y $ $m \neq 6xy+x-y $ $m \neq 6xy-x-y$ with any positive integers $x,y $.
-2
votes
0answers
28 views

Supposed p is a prime Number such that (p-1)/4 and (p+1)/2 are also primes. Show that p=13

$p$ is not $2$ or $3$ (otherwise $\frac{(p-1)}{4}$ would not be an integer).Hence p must be an odd prime. Also $p-1$ is divisible by $4$ $p = 4t + 1$ (say) $\frac{(p-1)}{4}=t$ $\frac{(p+1)}{2}=2t$ ...
3
votes
0answers
32 views

Why do we know that , besides the known idoneal numbers , there is at most one more?

Here https://en.wikipedia.org/wiki/Idoneal_number the definition of an idoneal number is given : A number $n$ is idoneal if there are no integers $a,b,c$ with $0<a<b<c$ and $n=ab+ac+bc$ A ...
1
vote
1answer
51 views

Let $P$ be a prime. Show that $\exists$ $x \in \mathbb{N}$ such that $f(x) = p$ then $\exists$ $y \in \mathbb{N}$ such that $g(y) = p$

What is given? $$\text{Let P be a prime}$$ $$\text{Let} \space f(x)= 3x+1$$ $$\text{Let} \space g(x)= 6x+1$$ Show that: If there exists $x \in \mathbb{N}$ such that $f(x) = P $ , then there exists a ...
2
votes
4answers
84 views

Should we or should we not take $1$ as a prime number? [duplicate]

I think I know that there were times in the past when it was convenient to look at a number $1$ as a prime number, and, as far as I can remember, even then it was dependent on who we ask is it prime ...
1
vote
1answer
28 views

The prime counting function has a lower bound of $C\log\log x$

I read that using Euclid's Theorem and by induction, a "gross underestimation" of the Prime Counting Function $\pi(x)$ can be stated as $C \log \log X$, i.e there is a constant $C$ such that the ...
-2
votes
1answer
35 views

Divisibility by 11 [on hold]

$xyzw$ is a 4 digit number such that x is even,y is smallest possible odd number,z is greatest prime no,w is a multiple of 3.if ($xyzw + n$) is divisible by 11 then n cannot be: a. 6711 ...
2
votes
1answer
43 views

If $0 < a < b,$ there exists an $x_{0}$ such that for $x \geq x_0$ there is at least one prime between $ax$ and $bx.$

My approach: I first showed that for $0 < a < b,~\pi(ax) < \pi(bx)$ if $x \geq x_{0}.$ Now, since $\pi$ is an integer valued function, $\pi(bx) - \pi(ax) \geq 1$ for all $x \geq x_0.$ i.e. ...
2
votes
0answers
23 views

Summing the digits of sum of the digits to obtain prime numbers

Define sum of digits (in base $10$) function as $sd_{10}(n)=\sum_{i=0}^ma_i$ where $n=\sum_{i=0}^ma_i \cdot 10^i$ and $0\le a_i\le 9$. If we choose prime number $86423$ and sum its digits we obtain a ...
49
votes
5answers
5k views

Are there an infinite number of prime numbers where removing any number of digits leaves a prime?

Suppose for the purpose of this question that number $1$ is a prime number. Consider the prime number $311$. If we remove one $1$ from the number we arrive at the number $31$ which is also prime. If ...
4
votes
1answer
43 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
30 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 ...
11
votes
3answers
117 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
53 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
35 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 ...
3
votes
3answers
44 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
706 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
46 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
65 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
33 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?
-1
votes
0answers
79 views

“Matrix sieve” - primes finding algorithm - is it useful for number theory? [closed]

I proposed "matrix sieve" algorithm for finding primes that in my opinion is simple, not needed operations of dividing and easy to memorize: In order to find all primes (up to a given limit) in the ...
2
votes
1answer
20 views

Half primes in the set

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
38 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
37 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
30 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
18 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
62 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
48 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
59 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
24 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 ...
0
votes
0answers
29 views

N as sum of k primes [closed]

How can we say if N can be represented as a sum of k prime numbers .If N=10 and k=2 it can be represented as sum of two primes (5+5) .How can we say this for any N and K .
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
52 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 ...
1
vote
0answers
37 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
76 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
29 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 ...
0
votes
0answers
21 views

Proving that ${p \choose r}$ is an integer for a prime $p$ and $0 < r < p, r \in \mathbb{Z}$ [duplicate]

I need to prove that given integers $p$ and $r$ such that $p$ is prime and $0 < r < p$, ${p \choose r} = \frac{p!}{r!(p-r)!} \in \mathbb{Z}$ As of now, I don't have any ideas on how to proceed. ...
2
votes
1answer
24 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
84 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
39 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
35 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
17 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 ...
6
votes
1answer
133 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. $$ ...
0
votes
0answers
24 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
41 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 ...