# Tag Info

## New answers tagged prime-numbers

1

$n\ge 4\Rightarrow 0<\overbrace{n^2\!+\!n\!-\!19}^{\large a(n)\ :=\ a_{\Large n}} \color{#c00}{< (n\!+\!1)^2}\,$ so a composite $\,a(n)\,$ has a proper factor $\,d\color{#c00}{\le n},\,$ thus $\,d\mid a(n\!-\!d)\,$ too,  by $\ a(n\!-\!d)\equiv a(n)\equiv 0\,\pmod{\! d},\:$ by the Polynomial Congruence Rule.

5

The kind of result that you may be looking for is called Linnik's Theorem, which states that if $\gcd(a,d) = 1$, then the smallest prime $q$ congruent to $a \pmod d$ satisfies $q \ll d^L$, where $L$ is Linnik's constant. The smallest known value of Linnik's constant is $L = 5$, due to Xylouris in 2011. That being said, the conjectured smallest possible ...

3

Suppose $n>4$ and $a_n$ is composite. Let $p$ be the smallest prime dividing $a_n$, so $$p^2\leq a_n=n(n+1)-19\leq 4n^2.$$ Hence $p\leq 2n$. Let $$k=\begin{cases} n-p&\text{if }n\geq p,\\ p-1-n&\text{otherwise}. \end{cases}$$ Then $k<n$ and $k(k+1)\equiv n(n+1)\equiv19$ mod $p$. Thus $p|a_k$, so $\gcd(a_k,a_n)\geq p>1$.

3

This is an interesting question. I hope others can also give responses. The key idea behind all the explicit formulas is to use contour integrals of $L$-functions to relate sums over the primes to sums over the zeros. The Weil and Riemann explicit formulas have similar statements and proofs, but neither is a strict specialization of the other. Briefly, ...

1

Let us take the formula apart slowly. First we have a product over all the possible divisors of $x$. The product will be zero if just one factor is zero, so claiming that $H(x)$ is 0 only if $x$ is not prime, amounts to claiming that if $x$ is composite, one of the factors will be zero - my guess is that we'll get a zero if $i$ is a factor of $x$. Then let ...

3

Your formula is essentially a computer program which iterates all integers in the range $[2,x−1]$. One can easily establish such formula, for example: $$F_n=\left\lfloor\frac{\left(\sum\limits_{k=2}^{n-1}\left\lceil\frac{{n}\bmod{k}}{n}\right\rceil\right)+2\cdot\left\lceil\frac{n-1}{n}\right\rceil}{n}\right\rfloor$$ The real challenge is to establish a ...

1

$(P_n,6)$ is a shorthand for $\gcd(P_n,6)$. So $(P_n,6)=1$ is just saying that neither $2$ nor $3$ divides $P_n$. $P_{n_0}=5^k$ is deduced from the fact that $P_{n_0}$ is not divisible by $2$ or $3$, yet its largest prime factor is supposed to be $5$.

2

Just to provide more than a handful of data. 1) This is the code I used in Pari/GP : list=vectorv(1000);li=0; {forprime(p=2,11333, \\ 11333 is just a "idle-typing" value f=factor(p-1); for(k=1,rows(f), q=f[k,1]; if((q^q-1) % p == 0 , li++;list[li]=[p,q,(p-1)/q ] )) );} list=Mat(VE(list,li)) ...

2

There are $168$ primes $p\lt 1000$ and you want to pick among them all $p$ such that for at least one prime $q$ divisor of $p-1$ one has $p$ divides $q^q-1$. So you want to have in the field $\mathbb F_p$ the equality $$q^q=1$$ It is clear that one has to test just the factor primes $q$ of $p-1$ such that $q^q-1\ge p$, therefore when $p$ increases, one can ...

4

Upper bound. If $p$ does not divide $10$, then there can be no such string of digits longer than $p-1$. Namely, consider all suffixes of your string (including the empty string) and compute the remainder of each of them (interpreted as a number) modulo $p$. If the string is longer than $p-1$ then there are more than $p$ different suffixes; by the pigeonhole ...

0

Let $f(n)=(-1)^n$, and $g(n)=-\mu\!\left(\frac{n\,}{\,2^{\nu_2(n)}}\right)\left\lceil 2^{\nu_2(n)-1} \right\rceil$. Furthermore, take the previous answer's advice, and set $n=2^km$ for odd $m$. Then their Dirichlet convolution satisfies $$(f*g)(n)=(f*g)(2^k)\cdot(f*g)(m)$$ First we will show that $(f*g)(1)=1$ and $(f*g)(m)=0$ for $m>1$. We have $$\... 1 Yes, your conjecture is true. To prove this, note that all divisors of n are of the form 2^kd where d is an odd divisor. Compute the sum that is equivalent to your original one:$$\sum_{\substack{d|n, \\ d\, \text{odd}}}\sum_{i=1}^{v_2(n)}(-1)^{2^{v_2(n)-i}}(-\mu(d))\left \lceil 2^{i-1} \right \rceil$$Note that if n is even, then all terms in the ... 2 One can show via the prime number theorem that $2\pi(x) - \pi(2x) \sim 2 \log 2 \frac{x}{(\log x)^2},$ so that 2\pi(x) \geq \pi(2x) for all sufficiently large x. See this answer. 1 COMMENT.-I wanted to verify your proposition by an example. I realized that the problem itself is very hard and would like to ask you some questions. 1) q and r should be both positive? 2) There is no uniqueness, is not it? 3) I do not have numerical programs that allow me to go up to 10000 but I tell you what I observed for p=7. If p^3=2q+r ... 1 Both f(x) and g(x) go to 0 as x \to \infty, so h(x) certainly has a global max and min somewhere on [11,\infty). All you need to do is find N such that, say, |f(x)| < 10^{-8} and |g(x)| < \cdot 10^{-8} for x \ge N, and then show that your maximum and minimum are the maximum and minimum on [11, N]. This is in principle a finite ... 2 Right now there are two competing methods for determining \pi(x) when x is large: the combinatorial method of Meissel-Lehmer-Lagarias-Miller-Odlyzko-Deleglise-Rivat (see here), which requires O(\frac{x^{\frac{2}{3}}}{(\log x)^2}) time and O(x^{\frac{1}{3}}(\log x)^2) space, and the analytical method of Lagarias-Odlyzko (see here), which requires O(x^... 1 It so happens that I got interested to that same problem recently, I named it in the same way (which is why I found this earlier post) and I met the same difficulties. If first wrote a computer program (in Python) to calculate the 'coverage' for the first i primes, on a set of N numbers, through "brute force". Essentially, it consists in running through all ... 3 These are just typical primes. No reason to give them a name because the majority of primes are of this "form" (and it's not so much a form as it is the absence of a form). Upper bound sieve theory shows that the number of primes up to x which are not twin/cousin/sexy is at most a constant times \frac{x}{(\log x)^2}, and it is conjectured that this is ... 1 In general let d be the common difference of an arithmetic sequence, where 3\nmid d, and let a, a+d, and a+2d be three consecutive terms in that sequence. Now WLOG if we assume 3\nmid a then we can write a and d as:$$a=3k+1\quad\text{ or }\quad a'=3k+2\quad\text{ and }\quad d=3j+1\quad\text{ or }\quad d'=3j+2$$for some j, k\in\mathbb{... 1 If d is relatively prime to b, then a + d j is divisible by b if and only if j \equiv -a d^{-1} \mod b. Thus exactly one of any b consecutive terms of the arithmetic sequence a, a+d, a+2d, \ldots is divisible by b. 3 If \,b\, is coprime to \,m\, then \,a+ib,\, i = 1,\ldots,m\, is a complete residue system mod \,m\, since$$\ a+ib \equiv a+j b \iff (i\!-\!j)b\equiv 0\overset{(b,m)=1}\iff i\!-\!j\equiv 0\iff i = j\,\ {\rm by}\,\ 1\le i,j\le mHence, being complete, it contains an element \equiv 0,\, i.e. a multiple of \,m. Remark \  When \,b = 1\, we ... 5 There is a simple, well-known theorem about that: If a, b and m are integers, m\ge 2 and \gcd(b,m)=1 then the set \{a,a+b,a+2b,\ldots,a+(m-1)b\} is a complete residue system. This implies, for example, that the set contains exactly one multiple of m. 3 Take a\in\mathbb{N} and suppose that a\equiv 1\pmod 3. Then \begin{align*} a&\equiv 1\pmod 3\\ a+10\equiv 11&\equiv 2\pmod 3\\ a+20\equiv 21&\equiv 0\pmod 3 \end{align*} If we instead have b\in\mathbb{N} such that b\equiv 2\pmod 3, then adding 10 to b is sufficient. The case in which we have \equiv 0\pmod 3 is obviously trivial. 1 Note that 2\cdot 3\cdot 5\cdot 7\pm1 is not a pair of twin primes: 2\cdot 3\cdot 5\cdot 7-1=11\cdot 19. 3 No, because although the number of unmarked numbers stay infinite, the sieve of Eratosthenes algorithm is very limited in predicting what numbers will stay unmarked before it gets to those numbers. Let's say n is a very large even integer, bigger than a googolplex. Clearly n is not prime, because it is a nontrivial multiple of 2. Maybe both n - 1 ... 1 I got an answer from elsewhere on this: Records from that era (i.e. 10+ years ago) are sometimes incomplete. The actual is-prime LL results are missing from the database. In the case of both of the exponents in the question, some anonymous user ran an LL check but their hardware was faulty and they came up with a false-negative result. 0 I tried this via Wilson's theorem- It seems to work but would be grateful if someone could verify it/offer improvements? Suppose a prime p=1 \ \text{mod} 4 . By Wilson's theorem,  (p-1)! = -1 (\ \text{mod} p) . But  p-r = -r (\text{mod} p)  So  -1= 1 (p-1) 2 (p-1)...( \frac{p-1}{2})( \frac{p-1}{2} ) = 1 (-1) 2(-2)...( \frac{p-1}{2})( \frac{p-1}... 2 Let\Psi(n,m,k)=100n^2+20nm+m^2+4k^2$$be a prime number for some (n,m,k) Then: This combination of (n,m,k) must not share any factors. Except (n,m) can share factors as long as:$$\gcd(n,m,k) = 1$$So:$$p = (10n+m)^2+(2k)^2$$For the expression above to be a prime number, a combination of (x,y) must be either even-odd or odd-even. But it ... 0 Not quite the answer but I can show that the collection of all uppermost slopes of B_a with a odd will contain infinitely many primes. Without showing any work or providing a proof you can see by inspection that if we take the uppermost slopes of B_a and place them column-wise into a matrix:$$B_3 = \text{ }\begin{matrix} 5&7&9&11&...

13

This question discusses the existence/infinitude of primes $p$ that can be written in the form $$p = q \pm 2^n$$ where $q$ is a prime and $n \in \mathbb{Z}^+$. In particular for $p = q - 2^n$, Gjergji Zaimi mentions in a comment to his asnwer that $$p = 47,867,742,232,066,880,047,611,079$$ is a counterexample.

1

Using the result of basic calculus in this link, we can say $$\lim_{n \to + \infty} \frac{1}{n} \sum_{k=1}^n e^{2 \pi i m p_k^{1/p_k}}= \lim_{p \to +\infty} e^{2 \pi i m p^{1/p}}$$ , where $p_i$ denotes the $i$-th prime number. Now, it is well known that $$\lim_{n \to +\infty}n^{1/n}=1$$ so that $$\lim_{p \to +\infty} e^{2 \pi i m p^{1/p}}=e^{2 \pi i m \cdot ... 2 I think this is an open problem. There is a famous conjecture due to Artin giving the density of the set of those primes p such that a non-square natural number a is a primitive root modulo p. Positive density, of course, implies that a is a primitive root modulo infinitely many primes p. Note that if a=b^\ell for some integer b and prime \... 3 As n goes to infinity, n^{1/n} approaches 1 from above. In particular the fractional part of n^{1/n} approaches 0, so the p^{1/p} are not equidistributed modulo 1 2 Since \ (k^2,p-k^2) = (k^2,p) = 1\iff (k,p) = 1,\, your criterion is equivalent to testing that \,p\, is coprime to all \,k\le \sqrt p,\  i.e. it is equivalent to the brute-force trial divisor factorization / primality algorithm that tests all integers below the square root of \,p\, as possible factors. Note that we need \,k\le \sqrt p\  not \, k ... 3 This is not enough. A counterexample is p=9. We must have 2\leq k < 3, so k=2. For k=2 we have k^2=4 and p-k^2=5 and \gcd(4,5)=1. However, when the last inequality is changed form a strict one into a non-strict one, it is true. So we should have for all integers 2\leq k \color{red}{\leq} \sqrt p that \gcd(k^2,p-k^2)=1. Suppose that ... 1 This is almost correct. If p is not prime, say p=k\cdot m with 2\le k\le m, then 2\le k\le\sqrt p and k\mid \gcd(k^2,p-k^2). Hence by contraposition: If p>1 and \gcd(k^2,p-k^2)=1 for all k with 2\le k\le\sqrt p, then p is prime. 1 This problem was asked in APMO 1997. You can find the solution here: https://mks.mff.cuni.cz/kalva/apmo/asoln/asol972.html Or you can even refer to this Art of Problem Solving thread: http://artofproblemsolving.com/community/c6h79669p456011 0 Number theoretical statement for the existance of infintly many such n: Let a_0=2, define a_{k+1}=2^{a_k}+2 for every positive integer k. Claim : (*)first property a_k | a_{k+1} (**)second property (a_k-1) | (a_{k+1}-1) Lemma : If a divides b and b/a is odd then: 2^a+1 divides 2^b+1 Proof of the claim by induction: ... 1 For a sum of three or more consecutive positive integers S = x + (x+1) + (x + 2) + ..... + (x + n -1) x > 0; n > 2 S = (x + n-1) + (x+n - 1) + (x + n - 2) + ..... + (x + 1)+x Add 'em together. 2S = (2x + n -1) + (2x + n-1) + .... (2x + n-1) = n(2x + n-1) Case one: n is even. Then S=\frac n2(2x + n -1) is not prime as n/2 > 1 ... 2 Let our sum be$$p=nx+n (n+1)/2\qquad n>2$$If n  is odd then (n+1)/2 is an integer and we can write p=nk , k\in\mathbb {N}  making p  composite. If n  is even then n/2=k' and we can write p  as$$p=k'(2x+[n+1])=k'd$$d\in\mathbb {N}  again making p  composite. Note that we must have n>2 because otherwise some of our factors will ... 1 The sum is as you said nx + n(n-1)/2. If n is odd it is a multiple of n as you said. Yet, if n is even it is a multiple of n/2. 1 for p prime and gcd(x,p) = 1 let$$f(x) = \frac{x^{p-1}-1}{p}$$by Fermat theorem x^{p-1}-1 = k p,y^{p-1}-1 = m p so (x^{p-1}-1)(y^{p-1}-1) = kmp^2 i.e.$$\frac{(x^{p-1}-1)(y^{p-1}-1)}{p} \equiv \frac{(xy)^{p-1}-x^{p-1}-y^{p-1}+1}{p}\equiv 0 \bmod p\implies f(xy) \equiv f(x)+f(y) \bmod p$$but this is not a discrete logarithm modulo p for ... 4 Note \,q(2k) = 6k+1,\ q(2k+1) = 6k+5 and every prime \,p>3\, has one of those forms, since by division \, p = 6q+r,\ 0\le r\le 5\, and \,2\mid 6k,\,6k+2,6k+4\, and \, 3\mid 6k+3 4 This is true. Let p>3 be a prime number. By division with remainder, we may write p=6q+r, where 0\le r<6. Now: r cannot be 0, because then p would be a multiple of 6. r cannot be 2 or 4, because then p would be a multiple of 2. r cannot be 3, because then p would be a multiple of 3. Therefore, r=1 or r=-1. ... 7 Since every prime above 3 must be of the form 6k \pm 1, where k \in \mathbb{N}_{>0}, it stands to reason that this expression, which is essentially 6k \pm 1 in different clothes, will produce all primes (in addition to the increasingly frequent composites). 0 We have those Mellin transforms for Re(s) > 1 :$$G(s) = \int_1^\infty (x-1) x^{-s-1}dx = \frac{1}{s-1}-\frac{1}{s}, \qquad F(s) = \int_1^\infty \frac{1-x}{\ln x} x^{-s-1}dx$$We see that$$F'(s) = G(s) \implies F(s) = \ln(s-1)- \ln(s) + C$$Then use the Euler product, again for Re(s) > 1 :$$\zeta(s) = \prod_p \frac{1}{1-p^{-s}} \implies \ln \...

1

Your have $(2p-1)! = \prod_{i=1}^{2p-1} j =p \prod_{j=1}^{p-1}j(j+p)$. Thus modulo $p^2$ this is $p \prod_{j=1}^{p-1}j^2= p ((p-1)!)^2$. Now one knows that $(p-1)!$ is congruent $-1$ modulo $p$; this is not hard to to show, and you can find it as part of a proof of Wilson's theorem. Thus in total we get that the result is $p$.

2

We have $$(p-1)! \equiv \frac{(2p-1)!}{p!} \equiv -1 \pmod p$$ by Wilson's theorem (edit: the division in the above expression is regular integer division, not modular division). So $\frac{(2p-1)!}{p} \equiv 1\pmod p$, or in other words, there is a $k$ such that $$\frac{(2p -1)!}{p} = kp + 1.$$Multiply both sides by $p$ to get $a = p$.

1

This can be solved intuitively by using a slight twist on Euclid's idea for generating new primes. Euclid employed $\,1 + p_1\cdots p_n$ is coprime to $\,c = p_1\cdots p_n.\,$ Stieltjes noted the generalization that, furthermore, $\ \color{#c00}{p_1\cdots p_k} +\, \color{#0a0}{p_{k+1}\cdots p_n}\,$ is coprime to $\,c\,$ too, which motivates the following ...

1

We give an elementary proof that does not use Dirichlet's Theorem. Let $P$ be the product of the primes that divide $z$ but do not divide $x$. (Recall that an empty product is equal to $1$.) Since $x$ and $P$ are relatively prime, there is a solution $n$ of the congruence $$xn\equiv -y+1\pmod{P}.$$ We show this $n$ works, by showing that $y+xn$ is ...

Top 50 recent answers are included