Prime numbers are natural numbers 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

3
votes
2answers
33 views

$\forall n\ /\ \not\exists$ {primitive roots modulo n}: if $\ Max(ord_n(k))+1 \mid n\ $ then $\ Max(ord_n(k))+1\ $ is prime?

When a number $n$ does not have primitive roots modulo n, $Pr(n)$, it is possible to generate the set $M$ of those numbers $m$ whose order $ord_n(m)$ is the maximum multiplicative order of $k$ in ...
22
votes
3answers
2k views

How to force prime numbers into a line?

Inspired by an article on Prime Spiral and Hough transform I tried to analyze patterns created by plotting numbers on spiral (Archimedean?). $$x = \cos( angle ) * radius$$ $$y = \sin( angle ) * ...
0
votes
0answers
14 views

system of congruency prime solutions

If you have a system of congruency and you have the solution space. Is there criteria to determine if there is a prime in the solution space and if yes is there a better way to find them instead of ...
0
votes
1answer
30 views

If $N\equiv 1\pmod 4$ does then follow that $p\equiv q\equiv 1\pmod 4$

$N = pq$ is the product of two primes. If $N\equiv 1\pmod 4$, does then follow that $p\equiv q\equiv 1\pmod 4$ ?
3
votes
1answer
28 views

Matrix with prime entries and largest possible determinant

Let $n\ge 1$ be a natural number. Arrange the first $n^2$ primes in a $n\times n$-matrix, such that the determinant becomes as large as possible. What is the largest possible determinant and which ...
2
votes
1answer
82 views

Special representation of a number

How can I check, if a number $n$ can be representated by $$pq+rs$$ where $p,q,r,s$ are pairwise different prime numbers with the same number of digits. For example, $$105153899965560312960 = ...
4
votes
1answer
44 views

Is there a counterexample? $\forall p \in \Bbb P\ ,\ p\gt 61\ ,\ \exists\ r1,r2\ \in \{\ Primitive\ Roots\ Modulo\ p\ \}\ /\ r1+r2 = NextPrime(p)$

This is the weirdest thing I have observed so far! Take the set of Primitive Roots Modulo p (link to definition here) of a prime number $p$, $Pr(p)$. For those primes $p \gt 61$ there is always a pair ...
0
votes
0answers
20 views

Counting the number of elements $x$ between $p$ and $p^2$ where lpf$(x(x+2))=7$

Let $p > 7$ be any prime. Let $f_7(p)$ be a function that counts the number of elements $x$ where $p < x < p^2$ and lpf$(x(x+2))=7$ where lpf is the least prime factor. It has been ...
3
votes
0answers
87 views

Conjecture concerning sums of reciprocals of largest prime factors

Let $x$ be an integer, $r(x)$ the reciprocal of the largest prime factor of $x$. Let $f(n) = \sum_{k=1}^{n-1} r(k) r(n-k)$ for which $k$ and $(n-k)$ are coprime. For $n = 3 \dots 10$, $f(n) = ...
0
votes
4answers
55 views

Prove or disprove $\frac{\left(2^{p}-2\right)}{p}\ \in \Bbb N, \forall\, p,\, prime$

Apologies in advance for poor formatting, not completely accustomed to typeset. What I ask is any non-particular value p, with one condition that it is prime, for which to disprove the following ...
-6
votes
3answers
113 views

Is this the real reason why 1 is not prime? [duplicate]

Divisibility by 1 is misleading as it does not divide a number into smaller parts. If divisibility by 1 is disallowed, then: The Unit: A whole number that is indivisible. Prime: A whole number that ...
3
votes
1answer
47 views

Is this reasoning correct for average prime gap?

Since \begin{align} &\operatorname{li}(n)\sim\Pi (n)\equiv\sum _{k=1}^{\lfloor \log (n)\rfloor } \frac{\pi \left(n^{1/k}\right)}{k}\\ \end{align} then the average gap for \begin{align} ...
0
votes
0answers
43 views

Solve an equation of the prime counting function

The problem is, Find all the positive integral values of $x$ for which we have, $$\pi(p_n-x)=\pi(p_{n+1}-x-1)$$where $\pi(x)$ denotes the number of primes not exceeding $x$. I don't know where ...
0
votes
1answer
30 views

Notation about factors

What is the name (if there is one) of the "full factorization representation" of a number, in which also the powers of the factors are (recursively) decomposed until all the numbers used in the ...
1
vote
0answers
78 views

Conjecture: for even n without primitive roots modulo n, the set of $m \in Max(ord_n(k))$ contains one pair of primes $p_1+p_2=n$ (Goldbach)

Conjecture: for those n even numbers that do not have primitive roots modulo n ,$Pr(n)$, the set $M(n)$ of those $k$ having a maximum multiplicative order $ord_n(k)$ contains at least a pair of primes ...
4
votes
1answer
61 views

A consequence of the inequality $\pi(x)+\pi(y)\ge\pi(x+y)$

Assume that the inequality $\pi(x)+\pi(y)\ge\pi(x+y)$ holds for all integers $x,y>2$ where $\pi(x)$ denotes the number of primes less than or equal to $x$. Then find all $m$ and $n$ such that, ...
2
votes
2answers
51 views

prime number problem:

How can I show that; For any prime $p,$ there exist $u, v\in\mathbb{N}\setminus{\{p\}}$ ( and depend on $p$) such that $\color{Purple}{p\mid uv}$ and both ...
1
vote
1answer
34 views

Is this bullet really needed in Furstenberg's proof of infinitude of primes?

See here . The bullet I'm referring to is: Any union of open sets is open: for any collection of open sets $U_i$ and $x$ in their union $U$, any of the numbers $a_i$ for which $S(a_i, x) \subset ...
0
votes
2answers
47 views

Let $p$ be a prime. Prove that $\sum_{i=0}^{p}\binom pix^i \equiv x + 1 \pmod p$

Let $p$ be a prime. Prove that $\displaystyle\sum_{i=0}^{p}\binom pix^i \equiv x + 1 \pmod p$. i got \begin{align} & \frac{p!}{i!(p-i)!}(x^0+x^1+x^2+x^3+x^4+\cdots+x^p) \\[4pt] = {} & ...
1
vote
2answers
38 views

What does “maximum order elements to mod n” mean for a number n without primitive roots modulo n?

I apologize because probably this is trivial, but I do not understand the concept: "maximum order elements to mod n for n". This is the context: in the Wikipedia in the primitive roots modulo ...
2
votes
0answers
37 views

How many entries in the sequence $x_n$ given by recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ are known?

The sequence $x_n$ with the recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ , where $p_k$ denotes the $k-th$ prime, has the following values : ...
0
votes
1answer
30 views

Diffie Hellman: Subgroup Confinement Attack

how can I solve the following tasks? a) Find all primitive elements of $\mathbb{Z}_{37}$. I guess the only possibility here is to try if the remainder off all elements from 1 to 36 to the power ...
-1
votes
0answers
33 views

Let p be a prime. Prove that $\sum_{i=1}^{p}({a}/{p})x^i \equiv x + 1 \pmod p$ [closed]

Let $p$ be a prime. Prove that $\sum_{i=1}^{p}({a}/{p})x^i \equiv x + 1 \pmod p$ I'm lost on this one. Any help would be appreciated
0
votes
0answers
43 views

Looking for a function which can serve as an upper bound to a count of the the pairs (x)(x+2) that have a given least prime factor?

Let $p \ge 7$ be a prime. Let $z > p$ also be a prime. Let $f_p(z)$ be the number of elements $x$ such that $z \le x < z^2$ and the least prime factor of $x(x+2) = p$ I am trying to find ...
1
vote
1answer
32 views

A question on Primes in Arithmetic Progression

We know that an arithmetic progression has to have a composite number since there are arbitrarily large gaps between primes. But I was wondering whether the following construction is possible: Can ...
1
vote
0answers
25 views

Estimating the number of elements with a given least prime factor in a sequence of consecutive integers

Let $a,n$ be any positive integers. Let $\varphi(x)$ be the Euler totient function. It seems to me that the number of elements $x$ with $a \le x < a+n$ that have a given least prime factor will ...
1
vote
0answers
57 views

Problem with multivaluedness of $(-1)^{\frac 14}$

Assume that $p\equiv3\mod4$ is an odd prime and $k$ an odd number. Then $$m=(-1)^{\frac{p^k-p^{k-1}+2}{4}}$$ seems to be always the value $1$ (?). This would be interesting how one can prove this - I ...
3
votes
1answer
90 views

Conjecture about the product of the primitive roots modulo a prime number ($\prod Pr_p$)

While I was learning about the primitive roots modulo $p \in \Bbb P$ (I will call $Pr_p$ to the complete list of the primitive roots module $p$) and having in mind the conjecture explained in this ...
1
vote
2answers
32 views

A question on perfect square

Prove that if $ab$ is a perfect square and $\gcd(a,b)=1$, then both $a$ and $b$ must be perfect squares. Their Answer: Consider the prime factorization $ab=p_1^{e_1}\cdots p_k^{e_k}$. If $ab$ ...
4
votes
2answers
32 views

Property of the sequence of primes

Let $p_n$ denote the $n$-th prime number. Does anyone know a proof of the following property? $$\forall n, n', \ p_n p_{n'} \geq p_{n+n'}$$ I'm surprised I can't find anything on this while I ...
5
votes
3answers
50 views

$a^{13} \equiv a \bmod N$ - proof of maximum $N$

From Fermat's Little Theorem, we know that $a^{13} \equiv a \bmod 13$. Of course $a^{13} \equiv a \bmod p$ is also true for prime $p$ whenever $\phi(p) \mid 12$ - for example, $a^{13} = a^7\cdot a^6 ...
3
votes
1answer
64 views

The number of primes in an interval

What is the smallest known $c$ so that for any $n\geq 2$ there are at least $n/\log_2{n}$ primes between $n$ and $cn$ (inclusive)? The prime number theorem seems to give an asymptotic result so I am ...
2
votes
0answers
29 views

If $q$ is a prime, $gcd(x(x+2),q\#)=1$ and $q < x < q^2$, doesn't it follow that $x,x+2$ are twin primes?

I recently asked a question that was not well received. That's ok. I don't disagree with the ratings if my question is unclear. I want to verify the foundation of my reasoning. Doesn't it follow ...
0
votes
3answers
151 views

Proving prime number combinatorics

I am trying to figure out the following review problem: Let $p$ be a prime number and $a$ be a natural number. Prove that the following (parts 1, 2, 3 and 4) are true for every $p$ and $a$. Here, ...
5
votes
2answers
36 views

A question about the proof that for prime p, p divides k(p), where k() is the Perrin sequence

Define the Perrin sequence by $k(1)=0$, $k(2)=2$, $k(3)=3$, and $k(n)=k(n-2)+k(n-3)$. We find that mostly $n$ divides $k(n)$ iff $n$ is prime, although there are a few exceptions called "Perrin ...
8
votes
1answer
83 views

How to find this number, which is probably a very big prime or a product of big primes?

Let $\mathcal{N}(n)$ be the next prime greater than $n$. Which is the smallest natural number $n>0\;$ such that: $\mathcal N(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot n)−2\cdot 3\cdot 5\cdot 7\cdot ...
3
votes
1answer
40 views

$n^{q}\equiv1~(\text{mod $p$})$ is possible solve this? [closed]

I have the following situation: Let $p, q$ be a prime numbers were $p>q$ and $n\in\{0,1, \ldots, p-1\}$. In this conditions is possible solve (in function of $n$) this equation, ...
1
vote
1answer
91 views

What is the next prime number?

Given an integer \begin{equation*} N~\text{such that}~N\leq 10^{18}, \end{equation*} what is the next prime number after this number? What approach should I use to solve this problem? (Problem ...
5
votes
3answers
888 views

One number divisible by all prime factors of another?

Given two numbers $x$ and $y$, how to check whether $x$ is divisible by all prime factors of $y$ or not?, is there a way to do this without factoring $y$?.
1
vote
1answer
31 views

Number of possible solutions in modular equation

I have given the result value $z$. I know that $$z \equiv x\cdot(x-1)\pmod p$$ where $p$ is prime and the value $p$ is fixed and given. I have also given the information, that $x \in \{m, M\}$, where ...
0
votes
2answers
475 views

How to determine if a number $A$ is divisible by all the prime factors of $B$?

How to determine if a number $A$ is divisible by all the prime factors of $B$? For example: $120,75$ $A=120=2^3\times3\times5$ and $B=75=3\times5^2$ Therefore yes, $A$ is divisible by the prime ...
1
vote
1answer
63 views

The following is a necessary condition for a number to be prime, from its digit expansion. Has it been referred somewhere?

Concerning a numbers’ digits we know some necessary conditions on them for the number to be prime, besides the last digit having to be odd (except for prime 2). For example in decimal representation ...
2
votes
2answers
36 views

PNT for composites

Is it true that \begin{align} &c_n\sim n+\operatorname{li}(n)+\operatorname{li}(n)/\log (n),\\ \end{align} where $c_n$ is the $n$th composite number? Is a better estimate known?
3
votes
3answers
90 views

For a prime $p\ge 17$ is $\dfrac{p^2-1}{24}$ ever a prime?

It was indicated in the comments of this MO question that if $p\ge5$ is a prime then $24|p^2-1$. Indeed $p=6k\pm1$ and $p^2-1=36k^2\pm12k+1-1=12k(3k\pm1)$ and exactly one of $k$ and $3k\pm1$ is even. ...
2
votes
2answers
30 views

Finding big exponential value

How to find the following most efficiently $$ A^{x} \bmod M $$ where $A,x\le10^{10}$ and $M$ is a quite big prime number.
2
votes
0answers
38 views

Prove an inequality of composite numbers

Yesterday after reading this post I tried to prove the inequality as given in the post. The inequality is, $$c_m+c_n>c_{m+n}$$ for all $m,n\ge1$. The problem was regarding the following special ...
2
votes
3answers
54 views

Why is it that if you square two prime numbers and add them, you get a number that is even and is not a perfect square?

If you do $x^2 + y^2 = n$ where $x$ and $y$ are both prime numbers and are both greater than $3$, why is $n$ always an even number that isn't a perfect square?
3
votes
1answer
45 views

Could all iterates of $s(n)=2n+1$ be composite for some starting $n$?

Let $s(n)=2n+1$ and $\sigma(n)=\{n,s(n),s^2(n),s^3(n),\ldots\}$, where $s^3$ denotes functions composition, $s^3(n)=s(s(s(n)))$. For example $\sigma(11)=\{11,23,47,95,\ldots\}$. As another example ...
0
votes
0answers
27 views

Reverse proof of Fermats Little Theorem [duplicate]

Let $n \in \mathbb{N}$. For all $x \in \{1,2,...n-1\}$ it is: $x^{n-1} \equiv 1 \text{ mod } n$. Show that $n$ is prime. This seems to be proving Fermat's little theorem the other way round. Until ...
0
votes
1answer
61 views

Are these two definitions of prime numbers equal?

In Coq for instance, prime numbers are defined ${n\ is\ prime} \doteq \forall a\in \mathbb{N}: a|n \rightarrow (a=1 \vee a=n)$ ...