# Tag Info

0

The first $k$ for which $n = \prod_{i \leqslant k} p_k$ and $\sigma (n) > 3n$ is $6$, here $n = 30030$. Also, $m = 240 < 30030$ is the least integer with $\sigma (m) > 3m$.

1

According to the (unproven) Redmond-Sun conjecture, your conjecture is false. Indeed, for $n,m>1$ your condition is equivalent to there being no prime strictly between $2^n$ and $3^m$. Redmond-Sun conjecture states that a gap between two powers doesn't contain a prime only finitely many times. If you believe that the list provided on Wikipedia is ...

2

There exists a theorem of Group Theory that says "if a prime $p$ divides the order of a finite group, this group has an element of order $p$". Thus, if all elements of $G$ have order $p$, then its order is a power of $p$.

3

Use Cauchy's Theorem, which states that for every prime $p$ dividing the order of a group $G$, there exists some $g \in G$ with order $p$.

-2

The implication "if a certain sufficient condition $(*)$ for Firoozbakht's conjecture is true for a maximal gap starting at a prime $p_k$, $k>9$, then it is also true for all prime gaps between this maximal gap and the next one" is shown in arXiv:1506.03042 (Journal of Integer Sequences, 18, 2015, article 15.11.2); see Section 4, Theorem 3 (page 4) and ...

3

Hint: Use strengthenings of Bertrand's Postulate, in particular Nagura's result that for $n\ge 25$ there is always a prime between $n$ and $n\left(1+\frac{1}{5}\right)$. We can use this to show that unless $k$ is very small, there are always at least $4$ distinct primes $p$ that satisfy $\lfloor \log p \rfloor=k$.

0

$\ln \left( \sum_{n=1}^\infty \frac{1}{n}\right)$ has no meaning. It is like you say $$\ln (\infty)=...$$ But $\ln x$ is defined on real numbers and not on "anything we understand". But everyone understands that Euler "understood" that the method was correct. This is why the proof is attributed to him.

0

Yes, it is. There is a theorem saying that given G is a finite group, G is a p-group iff |G|=p^k for some k. The proof requires Lagrange Theorem and Cauchy's Theorem.

1

Yes, in fact, the structure of the group $\mathbb{Z}/(n)^\times$ is known completely (see Wikipedia or the answers to this question; in particular, Hurkyl's answer sketches an elegant proof using the $p$-adic logarithm). In particular, from these descriptions one can easily deduce the following values for $k$. Let $a_p(n)$ denote the number of distinct ...

4

You just need to estimate the primes. We have $p_i\geq 2$.

0

$p_{2n+1} > p_{2n}$ for all $n$, thus $\frac{1}{p_{2n+1}} < \frac{1}{p_{2n}}$ for all $n$. Thus if $S_1$ converges so does $S_2$. Note that the sum of the reciprocals of sequence $(p_{2n+2})$ if and only if $S_1$ converges, because $$\sum_{n \in \mathbb N} \frac{1}{p_{2n+2}} = S_1 - \frac{1}{p_2}$$ $p_{2n+2} > p_{2n+1}$ for all $n$, so using similar ...

2

You can always say that $p_{2n}\le p_{2n+1}$, hence $\frac{1}{p_{2n}}\ge \frac{1}{p_{2n+1}}$ and thus $$S_1=\sum_{n=1}^\infty \frac{1}{p_{2n}}\ge \sum_{n=1}^\infty \frac{1}{p_{2n+1}}=S_2.$$ On the other hand, you have $p_{2n}\le p_{2n-1}$, which would imply that (recall that $p_1=2$) the $$S_1=\sum_{n=1}^\infty \frac{1}{p_{2n}}\le \sum_{n=1}^\infty ... 1 As p_{2n+1}>p_{2n}, we have S_1\ge S_2, so if S_1 converges then so does S_2. For the other direction, note$$S_2=\sum_{n=1}^\infty\frac{1}{p_{2n+1}}\ge\sum_{n=1}^\infty\frac{1}{p_{2n+2}}=\sum_{n=1}^\infty \frac{1}{p_{2(n+1)}}=\sum_{n=2}^\infty\frac{1}{p_{2n}}=S_1-\frac{1}{p_1}$$2 This is a well-studied problem, a key-word is "Linnik's theorem." Let us denote the least prime itself by p(a,b), so p(a,b) = b + n(a,b)a. It is more common to express results in that way, and one can pass from on to the other easily. Then Linnik proved p(a,b) \le c a^L for some constants c and L. Meanwhile the best constant L for which ... 3 HINT: Get a contradiction by showing that at some point, 7 must divide one of the numbers. Look at what happens to remainders mod 7 under a \to a^2+4 and (a,b) \to ab+4. 1 One can show that for each prime p there is a number ab+1\in T with p\mid ab+1. As this implies that a generating set must contain a multiple of p, T cannot be finitely generated. So, given p pick aprime b\ne p and see what simple condition for a you get ... 1 Hint: you only need to show that there are infinitely many primes dividing numbers in T. To start, let S be a finite set of primes and compare \pi_2(x) with how many numbers less than x are products of primes in S. 0 Modify to (P_n \pm 1) \cap P_l. This tool might help: Let P, Q be two proper subsets of \Bbb{Z} such that \Bbb{Z} = P \cup Q. Then (P \pm 1) \cap Q \not = \varnothing. Proof: If P \pm 1 \subset P, then P + \Bbb{Z} = \Bbb{Z} \subset P, which can't happen since P is proper. Clearly (P\pm 1) \cap Q can be finite, for example P = \{0\}, ... 0 The first statement is false: 2^{2^p-1} and k 2^{2^p-1} are divisible by 4, for example, but 2 isn't. So I hope that's not what you want to show. 1 For the first conjecture, this is true for any odd p that isn't divisible by 3, it is not very closely related to primes. This follows immediately from the fact that if p = 2n+1 and 3 \nmid p then n(n+1) is divisible by 6, so n(n+1)(2n+1)/6 (the exact formula for 1^2+\cdots +n^2, known) is always a multiple of 2n+1. I would guess this was ... 0 I.e. if xy is the least positive integer k such that a^k\equiv 1\pmod{m}, then prove two things: 1)\  \left(a^x\right)^y\equiv 1\pmod{m}. 2)\  There doesn't exist 1\le t<y such that \left(a^x\right)^t\equiv 1\pmod{m}. (1) follows from a^{xy}\equiv 1\pmod{m}. Prove (2) by contradiction: if such a t exists, then a^{xt}\equiv ... 1 Note that |\mathbb{Z}_p^*| = 2^k, so that every element has order a power of 2. Now, if a and b are non-generators, then |a| = 2^r and |b|=2^s for r, s < k. But then |ab| \le \textrm{lcm}(2^r, 2^s) = 2^{\max(r, s)} < 2^k, so that ab is also a non-generator. (Also, it's clear that |a| = |a^{-1}|, so the set of non-generators is also ... 1 No, it will not indicate composite when given a prime. The Miller-Rabin test, like many primality tests, uses properties that are always true for primes, but are rarely true for composites. Hence, barring implementation defects, it will always return true (PROBABLY PRIME) when given a prime. Most composites will return false (DEFINITELY COMPOSITE). Some ... 1 Let x = 2^n for convenience. There are x/4 ways to write x as a sum of two odd numbers. Of these, \pi(x/2) have a prime (or 1) in the first (lesser) component, and \pi(x) - \pi(x/2) have a prime in the second (greater) component. Therefore the number of pairs of odd composite numbers summing to x is bounded below by$$x/4 - \pi(x) \sim x/4$$... 0 Here is a sketch of a proof. Of course, the hard part lies in the results that are used for this sketch. A consequence of the Prime Number theorem is the nth prime number function p_n is asymptotically equivalent to \;n\log n (actually, it is equivalent to the Prime Number theorem). Hence \dfrac1{p_n}\sim \dfrac1{n\log n}, so that the series ... 7 Assume such a,b exist, wlog. d:=b-a>0. Let p be a prime >a. Then a+(p-a) prime implies b+(p-a)=p+d is prime. Hence by induction p+nd is primes for all n\in\Bbb N_0. In particular p+pd=p(d+1) is prime, which is absurd. 3 Let P be the largest known prime and m=\lfloor\sqrt P\rfloor. Then$$ m^2<P<(m+1)^2. $$Since P is the largest known prime, m is the largest integer known for which Legendre's conjecture holds. A different question would be to ask for the largest integer m such that the conjecture holds for all smaller integers. 2 This is not really a topology so much as a partition. Since \mathbb{Z}^+ = \coprod_{k\geq 0} P^k, each P^k is both open and closed in this topology, and so all we've really done is broken up \mathbb{Z}^+ into the sets P^0, P^1, P^2,\ldots and given each one the trivial topology. Many mathematicians have divided up the natural numbers by number of ... -1 σ(n) equals the sum of all divisors of n, not just the proper ones so the sum of the proper divisors of n equals σ(n) − n and similarly for m. Hence m and n form an amicable pair if and only if σ(m) − m = n and simultaneously σ(n) − n = m. Hence m and n form an amicable pair if and only if σ(m) = m + n = σ(n). 1 Hint : Use Euler's theorem : If p is a prime and p does not divide a, we have$$\large a^{\frac{p-1}{2}}\equiv\ (\frac{a}{p})\ \ \ (\ mod\ p\ )$$We have$$b^{x-1}\equiv (\frac{b}{2x-1})\ mod\ (\ 2x-1\ )$$Take it from here. 0 Given a set of indices K\subseteq \mathbb{N}, we can define the generalized prime zeta function$$ {\cal P}_{K}(s)=\sum_{k\in K}\frac{1}{p_k^s}, $$where p_k is the k-th prime. Following the thread of the proof that \prod p = 4\pi^2, we note that$$ \begin{eqnarray} e^{{\cal P}_K (s)} &=& \prod_{k\in K}\exp\left(p_k^{-s}\right) \\ ...

0

Theorem: The equation $ax+by=c$ is solvable if and only if $gcd(a,b)$ divides $c.$ Now, to answer your questions, it is immediate that gcd$(2^a,2^b-1)=1,$ since $2^a$ is even and $2^b-1$ is odd. Hence, by the above theorem, there exist integers $x$ and $y$ such that $$2^a\cdot x+(2^b-1)\cdot y=1.$$ Exactly which integers these are depend on $a$ and ...

0

The Fibonacci entry point $n_p$ is the least number with $p|F_{n_p}.$ Unless $p$ is a Wall-Sun-Sun prime, $p^2$ does not divide $F_{n_p}$. $n_p\le p+1,$ with $p$ dividing either $p+1$ or $p-1$ unless $p=5$. There are four cases to consider. If $p=2$ then either $\operatorname{ord}_2(F_n)\le3$ unless $12|n$ in which case $$... 0 The Miller-Rabin test doesn't need a perfect power test. See Crandall and Pomerance pages 135-136 for example. On the other hand, tests for the input being a perfect square are not uncommon in some Lucas and Frobenius tests. The former generally when searching for parameters where (P|n)=-1 which won't ever happen. But typically the test is put off ... 3 No because$$2as-4a-s-4=1\iff (2a-1)(s-2)=7\iff (a,s)=(1,9),(4,3)$$0 No. If a\ne 1, then in order for the expression to be prime, the other factor must be 1. But when a=1, this expression is 2s-4-s-4 = s-8, so we must have s=1. But then 2as-4a-s-4=1 and the product is 1. 1 Here is a more rigorous approach, which still involves a little trial-and-error. Note that pq-p-q=59 can be rewritten$$(1-p)(1-q)-1=59 \Rightarrow (1-p)(1-q)=60$$Clearly, with p and q both primes in \mathbb{N}, the factors a,b of 60 given by (1-p) and (1-q) respectively must be negative integers. This leaves the following cases for (a,b): ... 4 If pq - p - q=59, then (p-1)(q-1)=pq-p-q+1=59+1=60 Splitting 60 into pairs of factors, we might get:$$\begin{align*} 60&=1\cdot 60 \implies p=2, q=61 ; q-p=59\\ 60&=2\cdot 30 \implies p=3, q=31 ; q-p=28\\ 60&=3\cdot 20 \implies p=4, q=21 ; \ (\text{not prime})\\ 60&=4\cdot 15 \implies p=5, q=16 ; \ (\text{not prime})\\ 60&=5\cdot ...

0

Clearly, $pq-p-q=59$ for prime numbers $p,q$ when $q=11$ and $p=7$. $11*7-11-7$ $=77-18$ $=59.$. Rigorous Proof:- $pq-p-q=59$ After adding $+1$ on both sides and taking common we get, $(p-1)(q-1)=60$ Solving this equation yields the answer. Point to note is that there is no unique answer.So, goal should be to find consecutive primes so that ...

3

Ring theory has both the concept "prime element" and the concept "irreducible element". Each of these concepts is useful (or it wouldn't have been given a name), and it does not make sense to worry about which of the concepts is "better" or "right" without qualifying it with for such-and-such purpose. The fact that the concept of prime elements has taken ...

2

Just to elaborate on @Henning Makholm's answer: $p\equiv0\pmod3 \implies p=3 \implies p+4\neq5\text{ which is the next prime}$ $p\equiv1\pmod3 \implies p+8\equiv9\equiv0\pmod3 \implies p+8\text{ is not prime}$ $p\equiv2\pmod3 \implies p+4\equiv6\equiv0\pmod3 \implies p+4\text{ is not prime}$

11

One of $\{p,p+4,p+8\}$ will be divisible by $3$, so if they are all to be primes, one of them must be $3$ itself. Then we have $3,7,11$, which are all prime, but unfortunately 3 to 7 is not a gap, so no, there cannot be two consecutive prime gaps of length 4.

2

If $n = \prod_k p_k^{e_k}$ is the prime factorization of $n$, then $\varphi(n) = \prod_k (p_k - 1) p_k^{e_k - 1}$, and hence $$\frac{\varphi(n)}{n} = \prod_k \frac{p_k - 1}{p_k} = \prod_{p \mid n} \left( 1 - \frac{1}{p} \right).$$ In particular, this quotient only depends on which primes appear in the prime factorization of $n$ (and not on their ...

0

Let's denote the number by $F(n)$, for $n=0,1,2,...$ One can prove by induction that $37$ divides $F(n)$ for all $n$. This is easy to see if one uses Fermat's little theorem. I have certain problems with MathJax so I cannot write the full proof here. EDIT: 1) For $n=0$, we have $F(0) = 37$ which is divisible by 37. 2) For $F(n)$ we assume that $37$ ...

2

It is not known, but it is probably true. Note that PNT heuristically tell us that, if we call $r_{2}\left(n\right)$ the number of representations of $n$ as a sum of two primes, we have $$r_{2}\left(n\right)\approx\frac{n}{\log^{2}\left(n\right)}$$ hence, the number of representations grows if $n$ grows.

3

Hint: Try reducing modulo some small primes.

25

By Bertrand's postulate, you can find a prime satisfying $\lfloor n/2\rfloor <p< n$. Proceed by induction.

1

Things about primes and digits almost always amount to brute force. That's because base $10$ (or any base) is essentially an arbitrary system for representing numbers. Here, you have that every digit must be from $0,1,4,6,8,9$. Then you start eliminating: The number can't have $3+$ digits with have two or more digits $1$ because $11$ is prime (except ...

7

Suppose $n$ is the smallest number such that a number $m\ne n$ exists with $$n\ \phi(n)=m\ \phi(m)$$ Let $p$ be the largest prime factor of $n$ and $q$ be the largest prime factor of $m$. Then, $p<q$ is impossible because $n\ \phi(n)$ would not be divisivle by $q$. $p>q$ is impossible because $m\ \phi(m)$ would not be divisible by $p$. So, we have ...

1

As in the middle of November $2015$,there are no primes in the first $269293$ terms (!!), and it's very likely also that there are no primes in the first $300000$ terms. See the great Smarandache probable prime search managed by Serge Batalov.

Top 50 recent answers are included