Tag Info

New answers tagged

0

I thought you might enjoy the fact that the value of the infinite product $$\prod_p\frac{p^2+1}{p^2-1}$$ is $\frac{5}{2}$.


6

It's called the prime constant. When you enter that number into WolframAlpha and you see the $\mathcal{P} = 0.41468250985111166$, notice that in the bottom right-hand corner of that cell it says "$\mathcal{P}$ is the prime constant", which links to the Wolfram Mathworld page explaining what it is.


0

One direction is easy: Let the sequence be given by a numeric polynomial $f$. Then $mp^rf\in\mathbb Z[X]$ for some $r\ge 0$ and $m$ coprime to $p$. Hence $mp^rf(X+p^l)\equiv mp^r f(X)\pmod {p^l}$. With $l\ge k+r$ this gives us $f(x+p^l)\equiv f(x)\pmod{p^k}$ for all $x\in\mathbb Z$, i.e., the sequence is periodic. For the other direction we can use the ...


1

The following solution works for all $N \geq 9$. Let $y=5$ and $x=N-5$. Then we should have $$\pi(N) \geq \pi(N-5) + \pi(5) = \pi(N-5) + 3$$ Hence, at least three of $N-4$, $N-3$, $N-2$, $N-1$, and $N$ must prime. That is not possible unless $N-4=2$ or $N-4=3$, in which case we have $N \leq 7$. Contradiction. Note: We have $N \geq 9$ so that $x=N-5 \geq ...


2

As a reference point, there are 17193362135842433291 prime sums among primes up to $331$ (the 67th prime). That's as far as we can go using 64-bit arithmetic. For more values, see http://oeis.org/A071810 "Number of subsets of the first $n$ primes whose sum is a prime", where T. D. Noe has contributed a list up to the 100th prime.


3

Well let $p_k$ be the $k$-th prime and $f(k,n)$ be the number of subsets of the first $k$ primes that have a sum of $n$. Then obviously $f(k,n) = f(k-1,n) + f(k-1,n-p_k)$ for any $k \in \mathbb{N}^+$ and $n \in [1..\sum_{i=1}^{k-1} p_i]$. Since $\sum_{i=1}^{k-1} p_i \in O(k^2 \ln(k))$ as $k \to \infty$ by the prime number theorem, this algorithm will take ...


4

Mertens' Theorem says: $$\lim_{n \rightarrow \infty} \ \frac{1}{\log p_n} \prod_{k=1}^{n} \frac{1}{1 - \displaystyle{\frac{1}{p_k}}} = e^{\gamma}.$$ Euler's product formula for the $\zeta$ function and his evaluation of $\zeta(2) = \pi^2/6$ says that $$\zeta(2) = \lim_{n \rightarrow \infty} \ \prod_{k=1}^{n} \frac{1}{1 - \displaystyle{\frac{1}{p^2_k}}} ...


1

It is clear that the set of such primes is contained in the set of all integers of the form $m^2 + 1$, hence for any $\sigma > 1$, \begin{equation*} \sum_{p \in X} \frac{1}{p^{\sigma}} \leq \sum_{n \geq 1} \frac{1}{m^{2\sigma}} < \infty, \end{equation*} by the integral test. Hence, since $-\log(\sigma - 1) \rightarrow \infty$ as $\sigma \rightarrow ...


2

$r$ is the base of a Cunningham chain of the second kind. A Sophie-Germain prime is the base of a Cunningham chain of the first kind.


3

Statement (1) is fairly straightforward to prove once you notice that $\max_k(\text{ord}_n(k))$ is (by definition) the Carmichael function $\lambda(n)$. In particular, it is known that if $$ n = p_1^{e_1} \dotsm p_k^{e_k} $$ with $p_1,\dotsc,p_k$ distinct primes, then $$ \lambda(n) = \text{lcm}\big(\lambda(p_1^{e_1}), \dotsc , \lambda(p_k^{e_k})\big) $$ ...


3

Statement (2) seems to be false. $n=16269$ has no primitive root and the maximum order is $560$. $560+1$ divides $16269$ but is not prime. I used this brute force Perl program that took about 1.5 minutes: use ntheory ":all"; for my $n (3..100000) { next if znprimroot($n); my $m = vecmax(grep { defined $_ } map { znorder($_,$n) } 1..$n); ...


26

Loosely, what's going on here is that you're discovering the notion of residue class. If you look carefully, you'll discover that all of the points on your original spiral actually lie on a finite set of 60 lines through the origin: one line for every $6^\circ$ or for every $\frac\pi{30}$ radians. This means that what line a number is on is determined by ...


4

Let's fix some notation first: in polar coordinates an Archimedean spiral is a curve in the real plane (i.e. the "usual" plane with coordinates over the real numbers) $$ r = a + b \cdot \theta $$ for some fixed constants $a,b \in \Bbb{R}$ with $b \neq 0$. Here $r$ and $\theta$ represent the radius and angle of a given point, respectively. Now, inspecting ...


36

There are 2 behaviours going on here. In your last picture, it's easy to see that all numbers lie on the 6 rays through the origin. Why? This is because there are $2\pi$ radians in a circle, and you are incrementing by $\pi/3$ radians each time (which is 1/6 of the circle). This is why you are getting distinct rays. The other behaviour occurs when you only ...


0

No, it doesn't. For $p\equiv q\equiv 3\pmod 4$, $pq\equiv 9\equiv 1\pmod 4$. Since $p,q\equiv 1,2,3\pmod 4$, one has$$pq\equiv 1\pmod 4\iff p\equiv q\equiv 1\ \ \text{or}\ \ p\equiv q\equiv 3\pmod 4.$$


2

This is A180128 in the OEIS. You can do better for $n=4:$ $$ \pmatrix{53&11&23&13\\ 17&47&29&3\\ 7&5&43&37\\ 19&31&2&41}=4868296>4673460. $$ The fifth term is $$ \pmatrix{89&41&23&2&53\\ 31&97&29&47&11\\ 59&13&79&61&7\\ 37&19&5&83&67\\ ...


4

You said in a comment: I conjectured the uniqueness only for numbers large enough. It would be interesting, which is the largest counterexample (I think there is a largest). I think your intuition is backwards here, and I think it will be instructive if I explain to you why; this is also why I was able to immediately guess that there would be ...


2

Yes, it's probabilistic (in other words, it doesn't have anything to do with primitive roots or the next prime). The number of primitive roots modulo $p$ between $0$ and $p$ is $\phi(p-1) \gtrsim e^{-\gamma}p/\log\log p$ (using a known lower bound). In other words, the "probability" that a randomly chosen integer between $0$ and $p$ is a primitive root ...


0

Assume: p prime gcd(m,n)=1 m/n = p^(1/z) m^z = p n^z => prime factorization of m includes p to some power m = p q p^z q^z = p n^z p^(z-1) q^z = n^z => prime factorization of n includes p to some power but gcd(m,n) = 1, contradiction.


0

We answer only the last part of your question. If $q$ is a composite natural number such that $q$ divides $2^q-2$, then $q$ is called a Fermat pseudoprime to the base $2$. There are infinitely many Fermat pseudoprimes to the base $2$. The smallest is $341$. For a reasonable-sized list, more information, and references, please see this OEIS page.


0

No you cannot disprove the statement as this is exactly the Fermat's little theorem. For any integer $a$ and prime $p$, $a^p \equiv a \pmod p$ i.e. to say $p$ will divide $a^p-a$.


0

Observe that $$ 2^p-2=\sum_{k=1}^{p-1}\binom pk\equiv0\pmod p $$ Because $\binom pk$ for $1\le k\le p-1$ is always divisible by $p$.


1

By Fermat's Theorem, as others have pointed out, a prime $p$ greater than 2 always divides $2^{p-1}-1$. If you multiply that by 2, you get $2^p-2$ is also divisible by $p$, even if it is 2. Check out Fermat's Little Theorem for primes, and a similar theorem, Euler's Totient Theorem for numbers in general.


3

I don't think the reasoning is correct. It's pretty clear that $$ p_n-\Pi^{-1}(n)\sim\sqrt{\frac{n}{\log n}}\not\sim2\sqrt n\log n\sim\frac{2\sqrt n\log^2n}{\log n-2} $$ and I don't see any proof (or reason to expect proof) that the inverse of the partials gives the average gap size without further assumptions. In any case there's no justification for the ...


1

The real reason why $1$ is not a prime is because we define it not to be prime. Maths is simply nicer that way.


0

If you restrict it to simply natural number then your so-called new definition (Well you have worded it quite badly but I get the gist anyways) then your definition is indeed equivalent to the usual definition. However this definition is not useful and would not replace existing definition for a few reasons. One of which is how this generalises to general ...


0

First find the factors of it by factorisation second get the prime numbers involved in that say $(a,b,\ldots)$. E.g., $18=(2^1)(3^2)$. The prime factors are $2$ and $3$. Third formula: $$\text{No. of coprimes to $N$}= N(1-1/a)(1-1/b)\cdots$$


2

Take any two integers $m,n$ such that $mn-1 | p$ then $u=mp, v=np$ will work.


1

All $\binom{p}{i} \equiv 0$ unless $i =0, p$ so all these terms go away from the sum only the terms that remain are 1 and $x$. Hence the result. Or by using binomial theorem we have $\sum_{i =0}^{p} \binom{p}{i}x^i=(1+x)^p$ so now by Fermat's little theorem we have $(1+x)^p \equiv (1+x)$.


0

Note that $\pi(p_n) = 1 + \pi(p_{n-1}),$ so the right-hand side of the inequality (assuming $n > m$) is just $\pi(p_n) - \pi(p_m) = 1 + \pi(p_{n-1}) - (1+\pi(p_{m-1}))= \pi(p_{n-m+1}) - 1.$ Hence the inequality reduces to $\pi(p_n - p_m) \ge \pi(p_{n-m+1}),$ which holds iff $p_n-p_m \ge p_{n-m+1},$ since $p_{n-m+1}$ is prime. I doubt there's an easy way ...


2

$u=p, v = p+1$ work. I was just playing with it, so no constructive hint how to tackle this other than the obvious one that $u$ or $v$ or both need $p$ as a factor. Edit: you added the constraint $u, v \ne p$. Then $u=2p, v= 3p$ work. If you try to make both the numerators and the denominator multiples of $p$, in the form denominator $ip$, numerator $ki ...


0

There's a difference between modular arithmetic and equality. Unless you have coded your answer improperly, you've made an error in notation: The symbol congruence is a relation which has to do with mod n. An equals sign is a more (probably the most ubiquitous and fundamental) general relation. Equality is reserved for more fundamental answers. Mod n deals ...


2

They're just verifying the axioms for a topology, so the bullet is necessary. You could indeed reword it as you suggest though.


2

To find all the primitive elements you really need to find just one. Indeed, let $g$ be any primitive element modulo $p$. Then all other primitive elements have form $g^a$ where $a$ is coprime with $\phi(p-1)$. The key in DF key exchange schema is $k=g^{ab}$, so $k = m^b = n^a$ hence it is in $\langle m \rangle$ (because it is $k=m^b$) and similarly it is ...


1

My thoughts so far: 1) The property does make sense. The number you generate, $\prod Pr_n$, has a lot of small prime factors, which clearly cannot divide the gap to the next prime (in either direction), so the likelihood is that the next prime is less than $p_\times(n)^2$ distant, where $p_\times(n)$ is the smallest prime that does not divide $\prod Pr_n$. ...


1

No, this is impossible. Write your APs as $b_i + d_i n$, and assume $b_i>1$ (else shift the index $n$ until it is true). Now set $N = \prod_{j=1 }^m b_j$. Then $a_i(N)= b_i + d_i \prod_{j=1 }^m b_j$. This is divisible by $b_i$ for each $i$. So $a_i(N)$ is not prime for all $i$.


1

If $ab=2^4\cdot 3^2$ is $ab=(2\cdot 3)^{4\cdot 2}=6^8$? Because that's your argument. It is not true that: $$p^aq^b=(pq)^{ab}$$


0

Note that $$2^33^4\neq 6^{12}$$In fact $2^33^4=8\times 81=648$ is clearly not a square, and $6^4=1296\gt 648$.


2

We can use a few explicit improvements over Bertrand found on Wikipedia: [Nagura 1952] For $x\ge 25$ there is a prime between $x$ and $\frac 65 x$. Hence if $p_{n}\ge \left(\frac 65\right)^n$ and $p_{n'}>23$ then there are $n$ primes between $p_n'$ and $p_{n}p_{n'}$. Together with finitely many checks for $p_n\le p_{n'}\le 23$ this settles all cases ...


2

Assume $n\leq m$ (here I use $m$ instead of $n'$). By Rosser's theorem we have that $p_np_m>n\ln n\cdot m\ln m=nm\ln n\ln m$. For $n,m>8$ we have $nm\geq\frac{n+4}{2}\cdot m=\frac{1}{2}nm+2m\geq 2n+2m$. We further have for $n>e^2$ $\ln n\ln m>2\ln m=\ln m+\ln m\geq\ln n+\ln m$, so $p_np_m>nm\ln n\ln m> 2(n+m)(\ln n+\ln m)>2(n+m)\ln ...


1

Put $\ \color{#c00}{e = 13}\ $ below. $ $ For a simple proof of the theorem see this answer. Theorem $ $ (Korselt's Pseudoprime Criterion) $\ $ For $\rm\:1 < e,n\in \Bbb N\:$ we have $$\rm \forall\, a\in\Bbb Z\!:\ n\mid a^{\large\color{#c00}{e}}\!-a\ \iff\ n\ is\ squarefree,\ \ and \ \ p\!-\!1\mid \color{#0a0}{e\!-\!1}\ \, for\ all \ primes\ \ ...


1

Putting in $a=2$, we get that $N$ divides $2^{13} - 2 = 2 \cdot 3^2 \cdot 5 \cdot 7 \cdot 13$. On the other hand, putting in $a=3$, we get that $N$ divides $3^{13} - 3 = 2^4 \cdot 3 \cdot 5 \cdot 7 \cdot 13 \cdot 73$. Hence $N$ must divide $2 \cdot 3 \cdot 5 \cdot 7 \cdot 13 = 2730$.


2

Suppose that $a^{13}\equiv a\pmod N$, for every $a\in\mathbb Z$, then for every prime $p$ deviding $N$ we have $a^{13}\equiv a\pmod p$, but we have a primitive root $g$ modulo $p$, hence $$ g^{12}\equiv1\pmod p $$ which means that $p-1|12$, so $p\in\{2,3,5,7,13\}$. Hence the prime factors of $N$ are from the above set. Now I prove that the number $N$ is ...


1

Terry Tao's notes give a version of the prime number theorem in short intervals: $$ \sum_{x\le n\le x+y}\Lambda(n)\sim y $$ for $x\to\infty$ and $x^{3/4+\varepsilon}\le y\le x.$ So with $y=x\log 2$ $$ \sum_{x\le n\le x+y}\Lambda(n)\sim y $$ and thus $$ \pi(x+y)-\pi(x)\sim y/\log(x+y)+O(\sqrt{x+y})\sim x\log 2/\log x $$ and so 'all' that is required is finite ...


1

$1.$ Use directly $\dbinom pk=\dfrac pk\dbinom{p-1}{k-1}\enspace(k>0)$. If $k<p$, it is coprime with $p$, hence it divides $\dbinom{p-1}{k-1}$. This proves $\dbinom pk$ is a multiple of $p$. $2.$ $(1+ap)^p=1+p(ap)+\dbinom p2 (ap)^2+\dots+(ap)^p\equiv 1\mod p^2$. $3.$ $a^{p(p-1)}=\bigl(a^{p-1}\bigr)^p\equiv 1^p=(1+kp)^p$ (Little Fermat), then use $1$. ...


0

$$\binom pk=\frac{p!}{(p-k)!k!}$$ If $0<k<p$ then the factor $p$ in numerator does not get cancelled. $(ap+1)^p-1=\sum_{k=1}^{p}\binom pk (ap)^k$. Every term of the sum is clearly a multiple of $p^2$.


0

For part 1, write out $p\choose k$ in terms of factorials and think about what in the denominator could possibly cancel out the $p$ in the numerator.


0

Just wanted to say that there are two versions of what it means for a set of integers to be all relatively prime, each leading to a slightly different version of this Question: a) The greatest common divisor of all numbers is 1, and b) All pairs of numbers are relatively prime. The set {6, 10, 15} would be relatively prime under definition a), but ...



Top 50 recent answers are included