Tag Info

New answers tagged

7

If $m$ is not a prime, it factors into two numbers smaller than $m-1$, thus we have $m \mid (m-1)!$ and $(m-1)! \equiv 0 \mod m$ if those factors are different. If these numbers are not different, then it is sufficient to have $\sqrt{m}$ and $2\sqrt{m}$ as factors. As we have $2\sqrt{m}<m-1$ for $m\geq9$, the only other case is $m=4$, in which case we ...


2

The important thing is to keep yourself hidden. To my certain knowledge, three people found such a formula in the last twenty years. One in Berlin, one in Beijing, and one in Rio de Janeiro. All were found dead, with the brief version of the Riemann-Siegel Formula carved into their foreheads. There are those who cannot afford to let this knowledge become ...


1

First of all, I think there's only one place where I've seen $\mathbb{I}$ for the integers: http://mathworld.wolfram.com/Doublestruck.html I've seen $\mathbb{N}$ slightly more often, but then you get into the issue of whether $0$ is a natural number or not, so on that count I think you're better off using $\mathbb{Z}$, possibly with a $^+$ and a $\cup \{0\}$ ...


0

From the PNT we have that $\pi(x) \sim \frac{x}{\ln(x)}$, and seeing as we can write the average prime gap below $x$ as $\frac{x}{\pi(x)}$, we can write the average prime gap as $\sim \frac{x}{\frac{x}{\ln(x)}} = \ln(x)$. As $x\rightarrow \infty$, one could use LLN or some other probabalistic argument to give a heuristic argument that the ratio between the ...


4

In computer science (more precisely, when dealing with algorithms), the set of all primes (or, more accurately, of all representations of primes as strings in some alphabet), is generally denoted $\mathrm{PRIMES}$ or $\mathrm{P}\scriptstyle\mathrm{RIMES}$, as is usual to denote the language associated with some decision problem. See for example ...


6

Whatever you go with, remember that $\mathbb{P}$ is commonly used elsewhere, so make it very clear in your writing that you're defining it to be the set of primes. Personally, I've never seen $\mathbb{P}$ used to denote the primes, although apparently some do. For example, although the expression $\displaystyle \sum_{p \in \mathbb{P}} \frac{1}{p} = \infty$ ...


8

Relevant / duplicate / posted on MO: A symbol to denote the set of prime numbers. From the thread on MO, and from what I've seen elsewhere, the symbol $$ \Huge\mathbb{P} $$ is sometimes used. This doesn't really seem to be all too common though (not universal anyway).


3

As per the comments, here is an analytic proof (due to Euler) that can be generalised to the ring of integers of a number field (a number field is a finite extension $K$ of $\mathbb Q$, and its integer ring is the ring of algebraic integers contained in it). This can then be used to show that $\mathbb Z[\sqrt d]$ has infinitely many primes. (If $d \not\equiv ...


1

Graham conjecture We can determine a boundary for the first occurance of certain prime gaps if obeying one or more of the two conditions below. If both conditions are obeyed, then we determine that the first occurance of a prime gap is found following the condition which gives the lowest least bound. condition 1 -symmetric condition for symmetric type gaps. ...


1

The initial low density of the "errors" and the fact that initially most of them end in $9$ can readily be explained. I don't know what you mean by "isolate" in question $2$, and I don't think there's any need for further tests as referred to in question $3$. Except for the prime $2$ and the subsequent prime gap of $1$, primes are odd and prime gaps are ...


4

No. $(149,139)$ is the first pair of consecutive primes whose difference is $10$, but $$127-113=14>10. $$


6

It is not necessarily another prime, but it is most definitely divisible by another prime. For example, take $2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031$, which is not prime but divisible by $59$. It cannot be divisible by any one of those first $N$ primes, so it has to be divisible by some other prime (or possibly, a prime by itself, which also qualifies ...


1

Suppose there are only $n$ primes, $p_1,...,p_n$ and let $M=p_1...p_n+1$. If $M$ is composite, then there exists some prime $p_i$ which divides $M$. That is, there exists some $k$ such that $M=p_ik$. Note also that $p_i$ divides $M-1$. Therefore, there is some $\ell$ such that $M-1=p_i\ell$. Hence, we can write $M=p_i\ell+1=p_ik$. Alternately, ...


5

$$F_{3n}=F_{n+1}F_{2n}+F_nF_{2n-1}$$ You already know $F_{2n}$ is a multiple of $F_n$ so...


2

The Fibonacci have the following simple property: If $m |n$ then $F_m | F_n$. This property implies your claim.


2

It is known that if $n$ is prime, then $a^{n-1} \equiv 1 \mod n$ for all $2 \le a \le n-1$. Reading this backwards, we get: if we can find some $a$ between $2$ and $n-1$ such that $a^{n-1} \not\equiv 1 \mod n$, then surely $n$ is not prime. If not, then $n$ is prime. Therefore, you take the number $n$ to be tested and take $a=2$. If $2^{n-1} \not\equiv 1 ...


-4

Wilson's theorem states that a natural number $n > 1$ is a prime number if and only if $(n-1)!\equiv -1 \mod n$. We know that $1993$ is prime, thus $1992! \equiv -1 \mod 1993$, implying $1992! -1 \equiv 1991 \mod 1993$. It follows then that $1992! \equiv 1993k + 1991$ for some $k \in \Bbb Z^+$. $1992!$ is even (because it is divisible by $4$ and thus has ...


3

You can, but why let your computer "run" to bigger numbers, if running to $\sqrt{n}$ is enough? If $n$ is not a prime then $n$ admits a prime factor $p\leq \sqrt{n}$.


1

You haven't formalized what you mean by "the result is symmetric". The individual graphs are certainly not symmetric, you haven't specified a distribution whose symmetry we could inquire into, and if you had, it wouldn't be clear whether you could judge its symmetry by examining a couple of samples with the naked eye. So presumably what you mean is roughly ...


1

I will add here Steven Stadnicki's comments as an answer, so the question will be closed in some days (if other answers do not come): (1) is trivially implied, as you suggest, but (2) is not trivially implied. That said, it would be very surprising if the proof of Green-Tao could not be extended to handle your case - in fact, probably even the special ...


0

Not an answer, but another point of view $\prod_{i=1}^{k}p_i^ai=\sum_{i=1}^kp_i^2=(\prod_{i=1}^{k}p_i^{ai-1})*(\prod_{i=1}^{k}p_i)$ So it's a Hurwitz equation (More complete but in French) Lets call $A=\prod_{i=1}^{k}p_i^{ai-1}$ If there is a solution, for $k\gt2$ and $p_i\neq0$, we have $1 \leq A \leq k.$ We can put some restrictions on fundamentales ...


3

Of any three consecutive integers, one is divisible by $3$. In particular, one of $2^n-1$, $2^n$, and $2^n+1$ is divisible by $3$. But $2^n$ is not divisible by $3$, so one of $2^n-1$ and $2^n+1$ is divisible by $3$. If $n\gt 2$, then $2^n-1$ and $2^n+1$ are both bigger than $3$. One of them is divisible by $3$ and greater than $3$, so is not prime.


1

Hint: Primes other than 2,3 always have the form $6k + 1$ or $6k + 5$ for $k \in \mathbb Z$. To prove this, notice that numbers that have the form $6k, 6k+2$ or $6k+4$ are divisible by 2, and numbers that have the form $6k+3$ are divisible by 3.


0

Based on your examples, its not clear if the prime number is allowed to contain digits other than those specified, or if each of the digits specified can be used more than once. Assuming the answer to both of those is "no": The number $10235647$ is prime, and contains each of the digits $0$ through $7$ exactly once. For any number with the digits ...


1

Let $d_1,d_2,\dots,d_k$ be an arbitrary sequence of $k$ digits, with $d_k$ odd and not equal to $5$. Let $a=10^k$ and let $b$ be the number with decimal expansion $d_1\dots d_k$. By Dirichlet's Theorem, there are infinitely many primes in the arithmetic progression of numbers of the form $an+b$, so there are infinitely many primes whose decimal expansion ...


0

Is it clear that any $b$ in the form $p^{\beta_1}_{1} \cdot p^{\beta_2}_{2} \cdots p^{\beta_r}_{r}$ will divide $a=p^{\alpha_1}_{1} \cdot p^{\alpha_2}_{2} \cdots p^{\alpha_r}_{r}$ (with the constraints on all the $\beta_i$)? If so, we know that some divisors will have the form of some $b$. To show that all divisors have the form of $b$, we have to use the ...


1

Hint 1: How do exponents work? If $a > b > 0$ and $c \neq 0$ are all integers, then is it true that $c^b$ divides $c^a$? Hint 2: Start with small cases and specific examples to get the gears going. Let's say our number is $a = 5*2^4$. What are some divisors of $a$? $5$ is one. But so is $5*2$. And also, $5*2^2$. Do you see where I am going with this? ...


1

If $b$ divides $a$, then certainly any prime dividing $b$ must also divide $a$. In addition, though, if (say) $p^k$ divides $b$, then also $p^k$ must divide $a$. So the power of $p$ that appears in the factorization of $a$ must be at least $k$. Translating this into the language in your post, we have $\beta_1 = k$, and $\alpha_1 \ge k$, so that $0\le\beta_1 ...


2

Suppose there are about $f(N)$ losing points in $[1,N]$. There would be around $f(N+1)\approx f(N)+1f'(N)$ losing points in $[1,N+1]$, so $f'(N)$ is the chance that $N+1$ is a losing point. On the other hand the odds that $N+1$ is a losing point is the chance that all $N+1-a$ are composite. Pretend that the $N+1-a$ are all $O(N)$, then this chance would be ...


4

Below I've left my previous flawed approach. It is interesting that my upvoters and I hadn't noticed the highlighted mistake. And also that there exists a very straightforward proof: $$\prod_{m=1}^n\frac{p_m}{p_m-1}-\ln n>\sum_{m=1}^n\frac{1}{m}-\ln n>\gamma>0. $$ If you wish to avoid Mertens but not Rosser, note that your inequality is weaker ...


6

Assume $L$ is finite, say $\max L=m$. Then For any $n>m$ there exists $p$ with $n-p\in L$. As this implies that all prime gaps are $<m$, it is absurd. Hence $L$ is infinite.


4

We have $$\prod_{i\leq n}\frac{p_{i}-1}{p_{i}}=\prod_{i\leq n}\left(1-\frac{1}{p_{i}}\right)=\frac{1}{\log\left(p_{n}\right)e^{\gamma}}+O\left(\frac{1}{\log^{2}\left(p_{n}\right)}\right) $$ by the Mertens theorem. Now note that, by Rosser's theorem ...


0

Maple also says no: is((factorial(1992)-1)/(3449*8627), prime); $$\it{false}$$


1

I just ran a Rabin-Miller test on that number and I got the result "False" (i.e. it is NOT a prime number). If you want to know the divisors in addition to what you asked then I don't think that is computationally easy. >>> rabinmiller(a,1) False


1

yes, i think they are equivalent. If there are infinitely many twin primes, then for each $p,p+2$ we can find $n,n+2$ (just take $n=p-3$)such that your condition is satisfied, so $|T| = \infty$. Conversely, if $T$ is infinite, then for each $(n,n+2) \in T$ there is a pair of primes $p,p+2$ which is greater than $n$. So there are infinitely many of them. i ...


0

take any integer $n> 3$, and divide it by $6$. That is, write $n = 6q + r$ where $q$ is a non-negative integer and the remainder $r$ is one of $0$, $1$, $2$, $3$, $4$, or $5$. If the remainder is $0$, $2$ or $4$, then the number $n$ is divisible by $2$, and can not be prime. If the remainder is $3$, then the number $n$ is divisible by $3$, and can not ...


0

take prime factorization of $GCD(A,B)$. prime factors of $B$ must be subset of prime factors of $GCD(A,B)$.


0

This is false. For a sufficiently large positive integer Gaussian prime $p$, for $x=(p,1)$ we have $|x|\lt|p|+1/2$ but $|x|\gt|p|$.


7

Hint: Suppose $n$ is not prime, i.e. $n = bc$ for some integers $b,c \ge 2$. Then, $a^n-1 = a^{bc}-1 = (a^b)^c-1$ where $a^b > 2$. Now use your previous deduction. For the the last part "What can you say about primes of the form $2^n+1$?", suppose $n$ has an odd factor and use the identity $x^m+1 = (x+1)\left(\displaystyle\sum_{k = ...


16

No. The smallest prime factors are $3449$ and $8627$ (found with Mathematica). For what is worth: $$ \{n\in\mathbb{N}:2\le n\le2000\text{ and }n!-1\text{ is prime }\}=\\\{3,4,6,7,12,14,30,32,33,38,94,166,324,379,469,546,974,1963\} $$ Should have thought checking OEIS. This is secuence A002982


0

The prime numbers is the set of numbers derived by removing the set of composite numbers from the set of natural numbers. The pattern that the natural numbers follow is easily understood. The set of composite numbers also follow a discernable pattern:it is the union of the factors of 2, the factors of 3 etc. Therefore the prime numbers as defined in the ...


1

We can use the Legendre-Eratosthenes inequality $$\pi\left(x\right)-\pi\left(z\right)\leq\sum_{d\mid P\left(z\right)}\mu\left(d\right)\left[\frac{x}{d}\right] $$ where $$P\left(z\right)=\prod_{p\leq z}p,\, z\in\left[2,x^{1/2}\right]. $$ Then, taking $z=5 $ and $n $ sufficiently large we have ...


0

As you know (I hope :), $$\pi(n)\sim \frac{n}{\ln n};$$ so, you can say that $\pi(n)<n/k$ for any $k>1$ for sufficiently large $n$. But asymptotic behavior of $\pi(n)$ doesn't matter. For any integer $K>1$ and any prime $p$ we must have $\gcd(p, K)=1$ (if $K$ is not equal to some prime, of course, but in this case $\gcd(p,K)\ne 1$ only for one ...


5

Hint: Exepted for 2 and 3, primes are always congruent to 1 or 5 mod 6. To prove this, we see that if it is 0,2,4 mod 6, it is divisible by 2, and if its 3 mod 6 its divisible by 3.


1

Here is one more proof that $-4$ is a fourth power modulo $p$ (for $p \equiv 1 \bmod 4$.) Let $i$ be a square root of $-1$. Then $(1+i)^4=-4$.


3

Here is attempt to answer most of the questions raised: Is it true that $f(2k)=f(2k+1)$? This seems to be true, it would suffice to prove that $2|f(n)$ for all $n$. All algorithms to cover consecutive integers with multiples of primes use at a given moment all "small" primes, so they use in particular the prime $p=2$. However this does not prove that ...


11

Here's an elementary proof. From $p^2=a^2+2b^2$, we have $2b^2=(p-a)(p+a)$. Since $b\not=0$, we have $\gcd(a,b)=1$ and consequently $\gcd(p-a,p+a)=2$. Let's write $m=(p-a)/2$ and $n=(p+a)/2$, so that $\gcd(m,n)=1$ and $mn=2\beta^2$ where $\beta=b/2$. (It's easy to see that $b$ must be even.) Without loss of generality (since $a$ can be either positive ...


4

Let's assume that $p$ is odd and use a bit of algebraic number theory. Consider the field $\mathbb{Q}(\sqrt{-2})$, which has the ring of integers $\mathbb{Z}[-2]$. This is a Dedekind domain, so ideals factor uniquely, and so a PID. By the question we have $(p^2)=(p)^2=(a^2+2b^2)$ and we want $(p)=(c^2+2d^2)$, as then have $p=u(c^2+2d^2)$ for some unit $u$ ...


1

First we show that $d$ divides all of $2, 3, 5, 7$. Take some $q$ in the set $\{2, 3, 5, 7\}$. Since $2q < 15$ we know that there is a sub-sequence of terms of length $2q$ in our arithmetic progression. Now, if $q$ does not divide $d$, because $q$ is a prime, $d$ and $q$ must be coprime. So there must be two numbers in our progression of $2q$ terms that ...


1

It is true that $mx\in \Bbb{A} \;\;\forall m\in \Bbb{Z}/q\leq\Bbb{Z}$. The proof is as follows: Let $x\in\Bbb{A}$. By closure, $$ \underbrace{x+\cdots+x}_{\text{$m$ times, where $m\in\Bbb{Z}$}}\in\Bbb{A}.$$ As for your second query, note that $$\textrm{ord}(G)=q, \;\;q \textrm{ prime}\iff G\cong \Bbb{Z}/q.$$ Thus, up to isomorphism, there is a single ...



Top 50 recent answers are included