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

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
32 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
52 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
60 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 ...
1
vote
0answers
43 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
81 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
34 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
22 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
88 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
43 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
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 ...
7
votes
1answer
147 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
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
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 ...
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
15 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
53 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
49 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
59 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
20 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 ...
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
24 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
13 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
46 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 ...
0
votes
1answer
74 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$. ...
2
votes
0answers
36 views

Is there anyway to find how many prime factors has a composite number without knowing them?

Let's call f(n) the function that gives us the number of different prime factors of a composite number n For example: f(24)=2 Let's call g(n) the function that gives us the number of prime factors of ...
3
votes
2answers
35 views

Proof of (n) and (n+1) Sharing No Prime Factors

A number $(n)$ has a set of prime factors $\{\alpha_1, \alpha_2,...\alpha_\epsilon\}$ and a number $(n+1)$ has a set of prime factors $\{\beta_1,\beta_2,...\beta_\psi\}$. The conjunction, ...
1
vote
0answers
32 views

Prove that $p=13$, given that $(p-1)/4$ and $(p+1)/2$ are prime. [duplicate]

Suppose $p$ is a prime such that $(p-1)/4$ and $(p+1)/2$ are also primes. Show that $p=13$. I thought about taking $p_1=(p-1)/4$ and $p_2=(p+1)/2$ and proving that there is only one possible case ...
2
votes
0answers
39 views

Lehmann primality test

How to calculate final probability that a given number is prime after 1000 iterations, when using Lehmann primality test ?
1
vote
0answers
16 views

Lower bound on $\pi(x/2)$

I have seen the bound, $\pi(x/2)^2\gg\frac{x^2}{\log^2x}$ (In particular here http://staff.polito.it/danilo.bazzanella/PhD_files/Not%20always%20buried%20deep%20(Pollack).pdf page 212) Can someone ...
6
votes
2answers
67 views

How to prove $p^2 \mid \binom {2p} {p }-2$ for prime $p$?

How to prove $p^2 \mid \binom {2p} {p } -2$ for prime $p$? I have a hint: for $1 \le i \le p-1$, $p \mid \binom p i$. I cannot even start the proof. Please help.
3
votes
1answer
77 views

Fix $k∈\Bbb{N}$. An integer $n$ is said to be $k$-th power free if there exists no prime $p$ such that $p^k | n$…

Fix $k∈\Bbb{N}$. An integer $n$ is said to be $k$-th power free if there exists no prime $p$ such that $p^k | n$. Prove that for any $m∈\Bbb{N} $ greater that 1, there exists $m$ consecutive integers ...
5
votes
1answer
230 views

Conjectured primality test for $F_n(28)=28^{2^n}+1$

How to prove that following conjecture is true ? Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are ...
1
vote
1answer
71 views

What is the percentage of prime numbers among all numbers with 100 decimal digits?

I know the Prime Number Theorem, but 100 digits numbers are too big to be put in a calculator. Is there a way of finding out how many primes numbers as a percentage of the total numbers with 100 ...
1
vote
1answer
38 views

The exponent of $11$ in the prime factorization of $ 300!$ is___.

The exponent of $11$ in the prime factorization of $ 300!$ is $27$ $28$ $29$ $30$ My attempt: According to Exponent of $p$ in the prime factorization of $n!$ ...
2
votes
2answers
57 views

Natural numbers sorted uncountable?

$|\mathbb{N}|$ by definition is countable infinite. Going to sets of elements indexed by a finite number of indices labelling countable components yields again countably infinite sets (like when ...