Tag Info

New answers tagged

1

The strong Lucas test has a bound of 4/15. The extra strong Lucas test has a bound of 1/8. These don't have "bases" however, so you can't run them multiple times, and the cost is close to 2x a M-R test. The Quadratic Frobenius test has a bound of 1/7710 while taking in theory about 3x the cost. There are also the MQFT and EQFT tests based on the QFT. As ...


3

From $$p^x+q^y=p^s+q^t$$ if $(x,y)\neq(s,t)$, we have $$p^s(p^{x-s}-1)=q^y(q^{t-y}-1)$$ so $p\equiv 1\pmod q$ and $q\equiv 1\pmod p$. This is not possible. To find the exponents, if $n$ is not very big, the fastest and easiest way is perhaps bruteforcing. Remark: I have assumed that the exponents are positive. If they may be $0$ we have for example ...


1

$\qquad\quad$ I'm looking for some largeish (>10,000) easy-to-remember primes. $$1~234~567~891.$$


1

Together with a friend, I derived an answer. From the Integral expression written in the question, combined with the O result we get $$\pi(x)=\frac{x}{\ln x}+\int_2^x \frac{t}{t\ln^{2}t}dt+O\left(x\exp(-c\sqrt{\ln x})+\int_2^x\frac{t\exp(-c\sqrt{\ln t})}{t\ln^{2} t}dt\right).$$ The thing i missed in my calculations, was that the non-O expressions, can be ...


5

Here is a small list of some theorems and facts that go nuts if $1\in\mathbb P$. This is by no means comprehensive but it should grant some insight as to why this "choice" is the most natural one. Every natural number can be uniquely factorised into primes $$n = \prod_{i=1}^k p_i^{\alpha_i}$$ Where $p_i \in\mathbb P$ and $\alpha_i\in\mathbb N$. If ...


1

For those number crunchers out there I have included a number of further interrelated relationships between the number of goldbach partitions R(2n) upto 2n , the number of odd primes π(2n) upto 2n, and the number of twin primes T(2n) upto 2n . $$R(2n)=\frac{1}{2n}\sum_{k=0}^{k=2n-1}F^{2}(k)$$ ...


0

Since $\gcd(a^n-1, a^m-1) =a^{\gcd(n, m)}-1 $ (see $\gcd(b^x - 1, b^y - 1, b^ z- 1,...) = b^{\gcd(x, y, z,...)} -1$), $\gcd(a^p-1, a^q-1) =a^{\gcd(p, q)}-1 =a-1 $ since distinct primes are coprime.


5

Statement $A$: For any two positive co-primes $a$ and $d$, there are infinitely many primes of the form $a+nd$. Statement $B$: For $a=4$ and $d=3$, there are infinitely many integers $n$ such that $4n+3=2^{p}-1$ is prime. Your false argument: ${A}\implies{B}$.


5

The basic flaw is in the statement that, So, for $a=4$ and $d=3$, there exists infinitely many $p$ such that $2^{p}-1$ is a prime number. Dirichlet's Theorem (in this case) asserts only that there exists infinitely many primes of the form $4n+3$ but it doesn't say that infinitely many of them is of the form $2^n-1$.


2

Suppose that your condition holds, and let $a$ be any solution to $T^{\frac{p-1}{2}} \equiv -1 \pmod{p}$. Then $x\mapsto ax$ gives a bijection between the solutions to $T^{\frac{p-1}{2}} \equiv -1 \pmod{p}$ and the solutions to $T^{\frac{p-1}{2}} \equiv 1 \pmod{p}$. But then there are at least $\frac{p-1}{2} + \frac{p-1}{2} = p-1$ invertible elements in ...


1

Suppose $n>1$. Then $$p_r\cdot p_{r+1}\cdots \mid n-1$$ which means $$p_r\cdot p_{r+1}\cdots\leq n-1$$ The left hand side tends to infinity while the right hand side is a fixed number $n-1$. Bingo!


1

Assuming that you want to exclude the trivial case $n=1$: Hint: Since $A$ is an infinite subset of $\Bbb N$, $n$ is not an upper bound. Another way: $n<p_n$ (if $p_n\notin A$ take $\min A$ instead of $p_n$). Still another way: Take a prime divisor of $n!+1$. If it's not in $A$, take $\min A$.


3

If you allow $n=1$ your claim is false. If $n>1$ is imposed, just note that there will be a prime $p_i$ in your list greater than $n$ and $n$ is certainly not $1$ modulo this prime.


3

The short answer is yes, there are analogous series (and products). An early version of this inquiry can be found in Landau. At page 570 (vol.II) of Handbuch der Lehre von der Verteilung der Primzahlen he introduces $\lambda(n)$ and on page 618 introduces the equality $$\sum\frac{\lambda(n)}{n^s} = \prod(1 + 1/p^s)^{-1} = \frac{\zeta(2s)}{\zeta(s)}$$ in ...


1

If $\gcd(a,m) = d > 1$, then $\gcd(a^{m-1},m) \geq d > 1$ as well, so our conditions imply that $\gcd(a,m) = 1$. Now suppose $m$ is not prime, then the group $(\mathbb{Z}/m \mathbb{Z})^*$ has order $\phi(m) < m - 1$. The element $a \in (\mathbb{Z}/m \mathbb{Z})^*$ satisfies $a^{m-1} = 1$, so its order divides $m-1$. However this order also divides ...


1

This just adds some information about things you've already mentioned -- I'm quite interested as well in any methods. I note: To the authors’ knowledge, the only known prime generation algorithms for which the statistical distance to the uniform distribution can be bounded are the one proposed by Maurer [19,20] on the one hand, and the trivial ...


3

No, $1$ is not a prime number, though human mathematicians were slow to recognize this fact. The most important reason that $1$ is not prime (or composite, for that matter) is that it is its own inverse; just the fact that it has an inverse in $\mathbb{Z}$ speaks volumes.


3

You can see a graph and discussion of runtimes of some open source solutions, including BPSW (probable prime test), APR-CL, ECPP, and AKS in this answer to AKS usefulness. Reading your text, it looks like you might be asking "Did AKS have any impact on practical crypto implementations?", and the answer is "No." Going with Charles' example, 2048 bits is 617 ...


2

Here are my comments expanded into an answer which does not use Bezout's identity (I will in fact at the end use this to prove Bezout's identity purely using group theory). Let's take a more general setup and prove something a bit stronger: Let $G$ be any finite group and assume that $n$ is coprime to $|G|$. Then for any $x$ in $G$ there is a $y\in G$ such ...


1

It is interested to note that the zero order harmonic of the Fourier components of function $f(x)$ mentioned in PWMs post are $\operatorname{Re}\{F[0]\} = \pi[2n]$ and $\operatorname{Im}\{F[0]\} = 0$ and so their contribution to the sums $R(2n)$ and $\pi[2n]$ is $\pi^2[2n]/(2n)$ respectively, which is approximately $(2n/\log(2n))^2/(2n) = 2n/(\log^2(2n))$ ...


1

We have $p\ln\ln p = e(n)n\ln n\cdot\ln\ln(e(n)n\ln n) $ in which by the PNT $e(n)$ goes to 1 as $n$ gets very large. In this case $\sum\frac{1}{p\ln\ln p}\sim \int \frac{dx}{p\ln\ln p}$ and So $$I(n) = \int_3^n \frac{dx}{p\ln\ln p} = \int \frac{dx}{e(x)x\ln x\cdot\ln\ln(e(x)x\ln x)}$$ $$\sim \int \frac{dx}{x\ln x\cdot(\ln\ln x+\ln\ln\ln x)} $$ This ...


1

Note that holds $\underset{p\leq x}{\sum}\frac{1}{p}\sim\log\log x$ so by partial summation$$\underset{p\leq x}{\sum}\frac{1}{p\log\log p}\sim1+\int_{3}^{x}\frac{1}{\left(\log\log t\right)t\log t}dt=1-\log\log\log3+\log\log\log x\sim\log\log\log x$$ for $x\rightarrow\infty.$


4

$1$ is not a prime number, but it's important to understand that the ancient Greeks saw numbers mainly as geometric constructs, whereas we see them as algebraic constructs. We must also remember that the Greeks thought of the primes as "first numbers," and that survives in our terminology. For example, let's say you have $n > 0$ square tiles all the same ...


0

Equivalent to the statement you want to prove is its contrapositive: If $p$ is not prime, then there are $x,y\in \Bbb Z$ where $p|xy$ but $p$ divides neither $x$ nor $y$. Try some examples. Take $p=6$ and see if you can find $x,y\in \Bbb Z$ where $6|xy$ but $6$ divides neither $x$ nor $y$. Then try it with $p=8$ and $p=12$. Try to think of a general ...


0

Assume $p$ is not prime, then $(\exists a,b \in \mathbb{Z}^+)(a,b > 1 \wedge p = ab)$. Then $p \mid ab \wedge (p\nmid a \wedge p \nmid b)$, we received a contradiction with the assumption, so $p$ is prime. $\mathscr{Q.E.D.}$


4

The Dirichlet density of primes $p\equiv 1 \bmod 4$ and of primes $p\equiv 3 \bmod 4$ is both equal to $\frac{1}{2}$, but the number of primes up to $x$ in both classes can differ. This is what is meant by Prime number races ( see the answer of quid).


24

The phenomenon you observe is real. This is known, the case for $4$, as Chebyshev's bias Another relevant keyword is Shanks–Rényi race problem. "Prime number races" by Granville and Martin is a fantastic introduction to this circle of ideas. But, let me include some basic information here (more-or-less self-plagiarizing an MO-answer). On a rough scale ...


2

Perhaps you don't know it by the name "Bezout Equality", but it is probably the easiest way to go here. It says that if $\;x,y,\in\Bbb Z\;$ and if $\;\;$ g.c.d. $(x,y)=d\;$ , then there exist $\;m,n\in\Bbb Z\;$ with $\;mx+ny=d$ . In our case, there exist $\;a,b\in\Bbb Z\;$ s.t. $\;a\mathcal O(G)+bn=1\;$ , and then for any $\;g\in G\;$ we get ...


0

There is indeed a simple relationship between the total number of primes pi(2n) upto 2n and the total number of goldbach partitions R(2n) for that even number. $$R(2n)=\frac{1}{2n}\sum_{k=0}^{2k-1}a_{k}^{2}-b_{k}^{2}$$ and $$π[2n]=\frac{1}{2n}\sum_{k=0}^{2k-1}a_{k}^{2}+b_{k}^{2}$$ where a = Real{ F[k] } and b = Imag { F[k] } and F[k] is the Fourier ...


2

The problem is in "The generalized statement seems ridiculously strong to me...". While it's true that you're adding conditions it's also to so difficult to notice that you're not indeed adding any real strength. To see the problem more clearly consider the absolutely trivial: Any non-negative number $n$ is the sum of 4 squares Any non-negative number $n$ ...


16

Essentially, because your generalization doesn't add any strength. This already follows from the fact that it's derivable from Goldbach, as you've shown, but there's also a conceptual reason: as $d$ goes up the strength of the statement for that specific $d$ goes down drastically. In fact, we already know a version of the first step along your ...


2

Here's some sample code for finding an RSA key: http://www.cypherspace.org/rsa/rsakg.c It generates numbers uniformly at random, then tests them with mpz_probab_prime_p( , 25). Finding a 4096-bit RSA key require generating two 2048-bit primes. In this case mpz_probab_prime_p will do trial division up to 4096, and then up to 25 Miller-Rabin tests. About 1 ...


3

First of all, you do not need to invoke the fundamental theorem of arithmetic (existence and uniqueness of prime factorization). You only need that any natural number $>1$ has some proper divisor (by the very definition of prime as "$>1$ and only divisible by $1$ and itself"), hence among these is a minimal proper divisor, and that must be prime (as ...


3

Since $p_j$ is a prime, it must be somewhere in our finite set. Then we subtract to get $1=p_jq-p_1p_2\cdots p_k=p_j(q-p_1p_2\cdots p_k)$ by the left distributive property. This shows that $p_j$ is a prime which divides $1$. Since $p_j|1$ it follows $p_j\leq 1$. But (we know $1$ is not a prime! this is by definition) we assumed $p_j>1$ a prime.


0

(1) From rearranging the previous statement. (2) Yes from $p_j \mid 1$ you get $p_j \le 1$, which as you say contradicts $p_j$ being prime.


0

From the Wikipedia article on prime numbers: Most early Greeks did not even consider $1$ to be a number, and so they did not consider it a prime. In the 19th century, however, many mathematicians did consider the number $1$ a prime. For example, Derrick Norman Lehmer's list of primes up to $10{,}006{,}721$, reprinted as late as 1956, started with ...


3

I am so old I was taught that definition, that it's enough for a prime number to be divisible only by $1$ and itself. But my children and grandchildren were taught that a prime number must have exactly two distinct divisors among the positive integers. When I first heard about this redefinition, I thought it made sense. Because, you see, there were some ...


1

I think I will leave the part about squareclasses alone. Here is a diagram, of a design due to Conway, that organizes all column vectors $$ \left( \begin{array}{r} x \\ y \end{array} \right) $$ of integers $x,y$ such that $x^2 - 2 y^2 = 1,-1,2,-2,7.$ Conway's book can be downloaded from PDF. There is also a helpful discussion in Stillwell, Elements of ...


3

We can work this out with a little help from any program capable of computing with large integers (I used Maple and Haskell (ghci)): It turns out that $p-1=10q$ where $q$ is prime. Also, it turns out that $5^{5q}\equiv1\pmod p$, i.e., $2^{5qx}\equiv1\pmod p$. Since $2$ is a primitive root, this implies $5qx\equiv0\pmod{10q}$, and hence $x$ is even. Edit ...


1

We can show (using the PNT and using more or less standard notation here) that for sufficiently large $n$ there is an arbitrarily large $k$ such that $$n< p < (n+1/k)n$$ We can prove it in general--the trick is to find a specific $N$ so that if $n>N$ this will work for given k. Nagura proves it for $k = 5$ and other authors have found much higher ...


1

$$3\cdot2^{11484018}\equiv1\pmod p$$ $$\implies 3\equiv2^{^-11484018}$$ Now, $2^{p-1}\equiv1\pmod p\implies 2^{^-11484018}\equiv2^{p-1-11484018}\pmod p$


2

You know that Mod[a^(p - 1), p] == 1 In particular Mod[2^(p - 1), p] == 1 And multiplying by 3 Mod[3 2^(p - 1), p] == 3 Now we divide and multiply by 2 Mod[3 2 2^(p - 2), p] == 3 Rearranging: Mod[2 (3 2^(p - 2)), p] == 3 So x === (3 2^(p - 2))


1

For example, we can say, a prime is $1,3 \pmod 8$ if and only if there is just one expression $p = x^2 + 2 y^2.$ You get a little flexibility by throwing in indefinite forms: a prime is $1,7 \pmod 8$ if and only if there are just two infinite sequences of expressions $p = x^2 - 2 y^2,$ under the action (and its inverse) $$ \left( \begin{array}{r} x \\ y ...


0

$41$ is the only number in $A$ that is greater than $40$. And $5$ is the only one that is lesser than $6$. EDIT: And $29$ is the only one that nobody has yet mentioned...


1

It's been known since the early 1960s that $$n(\log n+\log\log n−3/2)<p_n<n(\log n+\log\log n-1/2)$$ for $n\gt19$, where $p_n$ denotes the $n$th prime. Of course all this says, for the example the OP gave, is $$884\le p_{168}\le1051$$ (after rounding the decimals up and down, respectively). The fraction $3/2$ in the lower limit has been improved ...


1

I think we should refer to the set itself and not to general properties. Thus, there might be a unique answer. Let $s(n)$ be the sum of the digits of $n$ and call $A$ our set. $11\notin A$ because $s(11)\notin A.$ Also, $11$ is the only number which cannot be obtained by adding or substracting (only once) the others, since we have $41=5+7+29$.


2

The rest are all Sophie Germain primes.


2

One of many possible answers: $7$ is the odd one out because every other number takes the form $$ n(n+1)-1 $$ for some natural number $n$. $5$ is the only one with a single syllable name in English.


4

This can be approximated by $f(n)=n\log n$ where the logarithm is natural (base $e$). A better approximation is $$ f_1(x)=x\log x+x\log\log x-x $$ and a still better approximation is the inverse logarithmic integral. Taking your example of 168, the three methods give 860, 967, and 934. (Here the second is best, but once the numbers get past 50,000 or so the ...



Top 50 recent answers are included