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

3
votes
2answers
237 views

How to understand Apostol's proof of the irrationality of $\sqrt{n}$ if $n$ is not a perfect square?

Recently I am reading the textbook of Apostol, Mathematical Analysis, Second Edition. On page 7, there is a theorem 1.10: If $n$ is a positive integer with is not a perfect square, then $\sqrt{n}$ is ...
9
votes
2answers
236 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 ...
5
votes
4answers
58 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 ...
1
vote
2answers
62 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
28 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?
6
votes
1answer
128 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. $$ ...
3
votes
1answer
36 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 ...
0
votes
2answers
39 views

Totien-Sum: why GCD( {n}/d, q/d) = 1; implies Sum{Totient(d/q) } = q

Have seen answer to this question. still don't understand.. Totient sum is defined: q = Sum(Totient (d) ); sum on all d : d|q More specific; The proof has these steps: 1. If d is a divider ...
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
votes
0answers
44 views

Primes finding algorithm [on hold]

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 in the sequence ...
2
votes
1answer
14 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
2
votes
1answer
33 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 ...
3
votes
0answers
277 views

The Divisors of $s(2s+1)$ and Primes $2n+1$ and $3n+1$ part 1

I want to check my math (and proof) on the following claim. The claim is by way of a computer search and a "hunch". claim: If $s$ is a prime number I write $\varphi_{s} =s(2s+1)$. Let $\tau$ be ...
1
vote
1answer
35 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)$ ...
9
votes
2answers
186 views

Numbers of the form $(p_{1}^{\alpha_{_{_1}}})^{2}+(p_{2}^{\alpha_{_{_2}}})^{2}+\cdots+(p_{n}^{\alpha_{_{_n}}})^{2}=(p_{m}^{\alpha_{_{_m}}})^{2}$

I'm looking for numbers of the form $$(p_{1}^{\alpha_{_{_1}}})^{2}+(p_{2}^{\alpha_{_{_2}}})^{2}+\cdots+(p_{n}^{\alpha_{_{_n}}})^{2}=(p_{m}^{\alpha_{_{_m}}})^{2}$$ where $p_{i}$ are prime numbers, ...
0
votes
0answers
29 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 ...
1
vote
1answer
61 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 ...
2
votes
1answer
47 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
56 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 ...
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
27 views

N as sum of k primes [on hold]

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 .
2
votes
1answer
82 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 ...
0
votes
0answers
29 views

Finding pseudoprimes using differences of prime products

Using the first nine primes $(2,3,5,7,11,13,17,19,23)$, what is the smallest (2nd smallest if $1$ is possible) difference that can be created using products of these primes? Rules are as ...
1
vote
1answer
42 views

Primality testing vs sieve

If the goal is to decompose an integer into its prime factors, is it better to use a sieve (such as the Sieve of Eratosthenes) or trial division up to the square root? Wikipedia has the statement ...
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
votes
2answers
74 views

Is this definition of Mersenne Primes correct? [on hold]

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
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 ...
27
votes
7answers
3k views

Can a complex number be prime?

I've been pondering over this question since a very long time. If a complex number can be prime then which parts of the complex number needs to be prime for the whole complex number to be prime.
6
votes
0answers
223 views

Complex prime numbers

I was just learning about how, if you multiply any two complex numbers together, you get a new complex number. With that in mind, is there such a thing as complex numbers that cannot be factored, or ...
12
votes
3answers
2k views

What is wrong with this proposed proof of the twin prime conjecture?

I was thinking on the twin prime conjecture, that there are an infinite number of twin primes... I came up with a proof. I have to think that it is incomplete or wrong, because many great minds ...
7
votes
1answer
110 views

Are there any known special properties of a number located between twin primes?

With the exception of $4$, every number located between twin primes is divisible by $6$. This one is obvious, but are there any other properties that can be ascribed to such numbers? A property may ...
1
vote
1answer
38 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 ...
70
votes
2answers
8k views

The square roots of different primes are linearly independent over the field of rationals

I need to find a way of proving that the square roots of a finite set of different primes are linearly independent over the field of rationals. I've tried to solve the problem using ...
1
vote
0answers
36 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
vote
1answer
28 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. ...
0
votes
0answers
45 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
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 ...
0
votes
1answer
24 views

Question about equations involving sum of powers modulo a prime

After reading an article by Peter Norvig about Beal's Conjecture I became pretty interested in digging into it. In his article here he goes into the use of a technique to optimize checking by this: ...
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 ...
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 ...
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
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 ...
5
votes
1answer
219 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
20 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" ...
2
votes
1answer
57 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 ...
1
vote
0answers
34 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 ...