# Tag Info

1

You can prove this by induction. The main step is the following Lemma: If $a \equiv b \mod rq$ for some $q, \, r$, then $a^q \equiv b^q \mod rq^2$. Proof: Suppose $a \equiv b \mod rq$, that is $a = b + krq$ for some integer $k$. Then by the binomial theorem $$a^q = b^q + q b^{q-1}\cdot krq + + \sum_{j = 2}^q \binom{q}{j} b^{q-j} (krq)^j = b^q +\ell r ... 0 Assume that there was some linear dependence relation of the form$$ \sum_{k=1}^n c_k \sqrt{p_k} + c_0 = 0 $$where  c_k \in \mathbb{Q}  and the  p_k  are distinct prime numbers. Let  L  be the smallest extension of  \mathbb{Q}  containing all of the  \sqrt{p_k} . We argue using the field trace  T = T_{L/\mathbb{Q}} . First, note that if  d ... 0 Omar Pol is the original author of the diagram, put online circa 2007. It appears that other similar works were derived from Pol's original diagram. A larger diagram (n = 1..16) is online at: http://www.polprimos.com/imagenespub/poldiv01.jpg (Source: Personal correspondence with Omar Pol.) 1 Generally we can say that if p is prime in some ring R and \mathfrak I is an ideal properly contained in \langle p\rangle, then the residue class \bar p is prime in R/\mathfrak I. Proof. \bar p is nonzero because we're assuming that \mathfrak I\subsetneq\langle p\rangle. It is not a unit because if \langle \bar p\rangle=R/\mathfrak I, then ... 1 Long comment: The commutative monoid (\mathbb{N}\setminus\{0\},\times,1) is freely generated (as a commutative monoid) by the prime numbers. In other words, for any commutative monoid X and any function f:\mathbb{P} \rightarrow X, there's a unique homomorphism \hat{f}:(\mathbb{N}\setminus\{0\},\times,1) \rightarrow X such that the restriction of ... 1 The function \ell on \Bbb N is the sum of prime factors (function), or a little less literally, the integer logarithm. P.A. MacMahon calls ell(n) the potency of n (see P.A. MacMahon, Properties of Prime Numbers Deduced from the Calculus of Symmetric Functions, Proc. London Math. Soc. (1925) s2-23 (1): 290-316.) The values \ell(1), \ell(2), \ldots ... 0 This is probably more like a long comment than an answer, but clearly some people have considered this earlier, because OEIS has sequences for them. Based on a simple search of p<2000 such that (b+1)^p-b^p is prime, I found these references: b=1: A000043: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, b=2: A057468: 2, 3, 5, 17, 29, ... 0 Hint If n \mid pq^4, then the prime factorization of n contains only factors of p and q (no more than one of the former and four of the latter). How many such numbers are there? 1 A pair of distinct prime numbers are primes p, q such that p \neq q. Multiplying two distinct prime numbers pq together gives a composite number whose prime factorization consists only of two primes. This composite number is divisible by 1, p, q, \text{and } pq. Nothing particularly fancy about them. 0 I'm using an answer to my own question to close this question because it doesn't seem that the formula can be made any simpler. If someone has an answer they are welcome to give it and I will probably accept it. 5 Just another point of view Suppose that a is divisible by a prime p. This means that:$$a = p \cdot k \Rightarrow p = \frac{a}{k}.$$Moreover, suppose that p > \sqrt{a}, then:$$\frac{a}{k} > \sqrt{a} \Rightarrow k < \sqrt{a}.$$This means that I can only use the primes p \in [\sqrt{a}, a] to determine if a is prime, instead of the set ... 3 This may be easiest to see if illustrated by example. Consider the factors of 16 as found by trial division. That is, we will divide 16 by 1 then 2 then... and each time the remainder is 0 we will record both the divisor and the quotient as a factor pair: 1: Yes, this yields the factor pair (1, 16). 2: Yes, this yields the factor ... 4 For every prime divisor of n that is less than n and greater than \sqrt{n}, there must be a prime number less than \sqrt{n} that divides n. This follows from the fact that it is impossible for a number n to have two prime divisors p and q that were both greater than \sqrt{n}, since then their product would be$$pq>(\sqrt{n})^2=n$$... 6 Let ab=p where a,b are possible factors of prime candidate p. If you find a factor b \geq \sqrt{p}, then a \leq \sqrt{p}. But if you checked all a \leq \sqrt{p} and didn't find any factors ... 20 Assume a is not a prime number. Then it can be written as a = bc with b, c \ge 2. Then the smaller of b, c is less than or equal to \sqrt a, for otherwise the product would be greater than \sqrt a \, \sqrt a = a. This smaller factor is then either a prime itself or has a prime factor that is even smaller. 10 Divisors come in pairs. If n divides a, so does a/n, as \sqrt{a}\sqrt{a}=a, one of the factors in a pair must be smaller than or equal to \sqrt{a}. 2 This is an extended comment, not an answer. The answer of user153012 to this question provides a link to a paper where your statement (which holds for primes other than 5) is proved. I also have an answer to that question, which, while not providing a proof of your statement, does suggest a generalization to composite numbers not divisible by 5. I do ... 0 same question here what a coincidence !!1!1! a) 4 b)all primes have 2 factors and by multiplying 2 primes you get 4 factors, the product of these factors must be divisible by 4 and 2 is the only even prime number however 2 x all the other primes NEVER equal a multiple of 4 therefore the answer is never an integer (basically, you can reword and explain ... 0 this is the contrapositive of if p is prime and p divides ab then p divides a or b which is a well-known result. to prove it, either p divides a and we are done, or it is coprime to a so there exist x,y st$$ xa + yp = 1 $$so$$ xab + yp = b $$p divides the left so it divides the right. Done. (see my book Proof Patterns for more ... 2 This inequality has to hold eventually. Counting only the semiprimes where one of the factors is 2, 3 or 5, we have$$ \pi_1(n) \ge \pi(\tfrac12 n) + \pi(\tfrac13 n) + \pi(\tfrac15 n) - 3 $$For any \alpha\in(0,1) and \varepsilon>0 the prime number theorem implies that all sufficiently large n will satisfy \pi(\alpha n) > ... 2 To summarize some of what I think the Comments are trying to say falsifies the "strong" version, let n be any odd composite number. Then 2n is not an "even semiprime" (since n is not prime). But if 2n were the sum of two even semiprimes, we should have n as a sum of two primes. Since this is possible only if n-2 is prime, it is pretty easy to ... 2 Given the prime p\neq 3, the integer number you are looking for is n(p) = 3^2p^2. It has 3^2 = 9 factors (1, 3, p, 3p, 3^2p, 3p^2, 3^2, p^2, 3^2p^2) and$$ \mbox{Factof}(n(p)) = \frac{3^2p^2}{3^2} = p^2 $$If p=3 then the number n(p)=2^2 3^3 = 108. In this case$$ \mbox{Factof}(108) = \frac{2^23^3}{2^2 3} = 3^2 $$2 'A prime no. always has two factors.' So the product of two primes p and q will have 4 factors: 1, p, q, pq Now if the primes are distinct then the product pq is not a multiple of 4 since 2 is the only even prime (and hence the other prime will be odd). So, \text{Factof}(pq) is not an integer. For (b) part, Number of factors of ... 1 Hint: consider the possibilities mod 3. EDIT: This was for the original question. For the new question, there seem to be infinitely many whenever a is a multiple of 3. This would follow from Dickson's conjecture. However, there is AFAIK no a for which this has been proven. For example, with a=3 we have q, 6q+1 and 12q+1 prime for q = ... 0 Rosser and Schoenfeld proved that for X \ge 17 there are at least N primes less than or equal to \dfrac X {\ln X}. So, choose X so that \dfrac X {\ln X} \ge N. 1 Since \pi(x)\sim\frac{x}{\log x} by the PNT, p_n behaves like n\log n. You may use Chebyshev's weak version$$C_1\frac{x}{\log x}\leq \pi(x)\leq C_2\frac{x}{\log x}$$to deduce explicit (enough) bounds for p_n. Anyway, unless n is extremely small, there are at least n primes in the range [2,n\log^2(n)]. 1 No, it isn't true. If you must have a period which is an integer number of hours, any period which is relatively prime to 24 (that is, doesn't share a prime factor with 24) will only hit the same time of day after 24 repetitions. For example: 25 hours would be an hour later each day until it works through all possible times and back to the starting time. As ... 0 The design somewhat contradicts the stated reasons for choosing 29. The reset time is specified not in hours but in minutes, 1740 = 29 \times 60. By taking it to be a multiple of 1 hour, there is a synchronization of the resets with the hours of a 24 hour clock, which makes the possible period lengths 60 times shorter. The designers created ... 2 With a little linear algebra, that at this stage is usually well known already, I think it can be pretty easy and short: For any \;n\in\Bbb N\;,\;\;\Bbb F_{p^n}\; is a linear space over the prime field \;\Bbb F_p\; and of dimension \;n\; , so:$$\Bbb F_{p^a}\hookrightarrow\Bbb F_{p^b}\iff \Bbb F_{p^a}\;\;\text{is a linear subspace of}\;\;\Bbb ...

1

If integer $r$ is the length of the reset interval, and resets begin at $t=0$, then the sequence of reset times (as measured on a $24$-hour clock) is $$R_{24,r} = (t\ \mathtt{mod}\ 24:\ \ t\ \mathtt{mod}\ r=0,\ t\in \{0,1,2,...\} )$$ where $\ a\ \mathtt{mod}\ b\$ denotes the remainder of the division of $a$ by $b$. NB: If $q,r$ are positive ...

1

There is a conjecture which states that the total number of writing $n$ as a sum of two odd primes is $\sim \frac{n}{2(\ln n)^2}$. This shows that the sum of two twin primes will be a sum of two other primes as well. So, your conjecture is a special case of an older conjecture. (But ,I always liked elementary conjectures too,so do not be disappointed if ...

2

Your question could be formally written as Every prime number is an adjacent of multiple of six with two exceptions ($2,3$). Which is a well known result. Here goes an elementary proof For any integer $n$ write $$n=6q+r, \qquad \mbox{where } q\in \Bbb Z^+ \mbox{ and } r=\{0,1,2,3,4,5\}$$ If $r=\{0,2,4\}$, then $2|n$ and $n$ can't be prime. If ...

2

yes, see: https://en.wikipedia.org/wiki/Bertrand%27s_postulate --> "Better results"

1

Finding a prime gap of length $am$ that starts above $b$ will certainly do it -- and since there are arbitrarily long prime gaps this is always possible. (This is essentially Henrik's answer to the linked question).

3

A well known way of generating a sequence of $n$ consecutive numbers that aren't prime is to consider $(n+1)!+2, (n+1)!+3,\ldots, (n+1)!+n$ - it's quite obvious that each of these numbers are divisible by $2, 3,\ldots, n$. We could perform that for $n=65$, the generated sequencemust contain five consecutive elements of your sequence, thus producing a ...

2

Consider the system of congruences $$13x\equiv -11\pmod{2}, \quad13(x+1)\equiv -11\pmod{3},\quad 13(x+2)\equiv -11\pmod{5},\quad 13(x+3)\equiv -11\pmod{7},\quad 13(x+4)\equiv -11\pmod{11}.$$ By the Chinese Remainder Theorem, this has infinitely many solutions. So there are infinitely many consecutive $5$-tuples of our sequence which are respectively ...

2

No, because the density of primes in this, and any other, arithmetic progression is 0. See https://en.wikipedia.org/wiki/Dirichlet's_theorem_on_arithmetic_progressions for details.

4

(I prefer the notation $\displaystyle \sum_{j=1}^n 1_{j | n^j} 1_{ n | j^n}$, and using that for integers $\lfloor \frac{a}{b}\rfloor-\lfloor \frac{a-1}{b}\rfloor= 1_{b|a}$, and $rad(n) = \prod_{p | n} p$) we get $$1_{ a | b^a} = 1_{ rad(a) | b} = 1_{ rad(a) | rad(b)}$$ thus $$1_{j | n^j} 1_{ n | j^n} = 1_{ rad(j) | rad(n)}1_{ rad(n) | rad(j)} = 1_{ ... 4 Let \omega(n) (OEIS A001221) represent the number of distinct prime factors of n. Then a (fairly) transparent expression for what you want is$$\sum_{1 \leqslant k \leqslant n} [\omega(k) = \omega(n) = \omega(\gcd(k,n))],$$where [\cdot] is the Iverson bracket, equal to 1 when the condition inside is satisfied and 0 otherwise. So we're tallying ... 1 Note that p_1\mid k_2 and p_2 \mid k_3. Let k_2 = a_1p_1, k_3 = a_2p_2. Choose p_3, p_2, a_2. k_2 = a_2p_3 - 2. k_3 = a_2p_2. Choose p_1 from the prime factors of k_2. a_1 = k_2 / p_1. k_1 = a_1p_2 - 2. Now the requirement that k_3 \ge p_3 requires that a_2 \ge p_3/p_2. That k_2 \ge p_2 requires a_1 \ge p_2/p_1, but ... 5 For concrete bounds on prime gaps that improve upon "Bertrand's postulate", which (in a slightly weakened form) states:$$ \forall n \ge 3 \;\exists p \text{, a prime s.t. } n < p < 2n $$see a brief summary on the Prime Pages. In particular:$$ \forall n \ge n_0 \;\exists p \text{, a prime s.t. } n < p < (1+\epsilon) n $$holds for ... 3 This is a general algorithm to take a prime, in particular an odd prime p, and express it as the value of an indefinite binary form of discriminant \Delta. The requirements are that \Delta > 0, that \Delta  is NOT a perfect square, and that \Delta is a quadratic residue \pmod p. In particular, p does not divide \Delta. With large class ... 4 I don't know much about field theory but within the laws of elementary mathematics, note that by Thue's Lemma we have$$x \equiv uy \pmod p$$For u^2 \equiv 2 \pmod p, such that 0<|x|,|y|<\sqrt{p}. Then proceed to notice$$x^2-2y^2 \equiv 0 \pmod p$$Then notice$$-2p<x^2-2y^2<p$$So x^2-2y^2=0 or x^2-2y^2=-p. I believe you can proceed ... 1 Let p be a prime congruent to 1 modulo 4, and suppose that r_1^2\equiv -1\pmod{p}. Let r_n=r_1^{p^{n-1}}. We show by induction on n that r_n^2\equiv -1\pmod{p^n}. For the induction step, suppose that for the positive integer k we have r_k^2\equiv -1\pmod{p^k}. We will show that r_{k+1}^2\equiv -1\pmod{p^{k+1}}. By the induction ... 6 Yes, just take x_0=2p and then x_1=p. 9 An element \overline{a} (where 0\leq a \leq n-1) of the ring \mathbb{Z}/n is invertible precisely when a is coprime to n by a standard result of elementary number theory. The number of positive integers less than or equal to n which are coprime to n is given by the euler-phi function. Hence it suffices to compute \varphi(p^n). You can show ... 9 Let G=\mathbb{Z}/p^{n}\mathbb{Z}. Lemma. For a,n\in\mathbb{N}, ax\pmod{m}=1 has a solution if and only if \gcd(a,m)=1. Proof. ab\pmod{m}=1\iff m\mid ab-1\iff\exists k\in\mathbb{N} such that mk=ab-1\iff1=a(b)+m(-k)\iff\gcd(a,m)=1.// Now, by our lemma we know that the invertible elements in G are precisely those that are relatively prime to ... 2 \begin{array}{rcl}p^2-1 &=& (p+1)(p-1) \\\\ &=& (6k\pm1+1)(6k\pm1-1) \\\\ &=& (6k+2)(6k)\ \text{or}\ (6k)(6k-2) \\\\ &=& 12k(3k+1)\ \text{or}\ 12k(3k-1)\end{array} 9 Since p^2-1=(p-1)(p+1) and p is odd, you have that p^2-1 is the product of two even numbers, hence their product is divisble by 4. Further, one of p-1,p,p+1 is a multiple of 3, but since p is prime, it is not p, hence the product is divisible by 3. Therefore, the result is divisible by 3*4=12. Actually, given two consecutive even ... 2 Since u know that any prime ≥5 can be represented as 6 k±1 so,$$p=6 k±1p^2=36 k^2 ± 12 k + 1p^2=12(3 k^2 ± 2 k) + 1p^2-1=12(3 k^2 ± 2 k) + 1 -1p^2-1=12(3 k^2 ± 2 k) Which is divisible by $12$....(Q.E.D)

Top 50 recent answers are included