New answers tagged

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±1$$ $$p^2=36 k^2 ± 12 k + 1$$ $$p^2=12(3 k^2 ± 2 k) + 1$$ $$p^2-1=12(3 k^2 ± 2 k) + 1 -1$$ $$p^2-1=12(3 k^2 ± 2 k)$$ Which is divisible by $12$....(Q.E.D)



Top 50 recent answers are included