# Tag Info

5

We can write $$x^2-xy+7y^2=\Big(x-\frac{1+3\sqrt{-3}}{2}y\Big)\Big(x-\frac{1-3\sqrt{-3}}{2}y\Big)$$ so (since $\mathbb{Q}(\sqrt{-3})$ is a PID) determining which primes can be written in the form $x^2-xy+7y^2$ reduces to the question of which primes split in $\mathbb{Q}(\sqrt{-3})$. If $p$ is an odd prime, then $p$ splits in $\mathbb{Q}(\sqrt{-3})$ if ...

1

In your setting, we have 1. $q$ is prime 2. $4q+1$ is prime 3. $6q+1$ is prime Your questions is whether $4q^2 +1$ is prime. Running the following program in SAGE, we find that $4q^2+1$ is not prime for $q=277$. for p in primes(100000): if is_prime(4*p+1)==1: if is_prime(6*p+1)==1: if is_prime(4*p^2+1)==0: ...

4

We need a more information than just the PNT. What we need the following refined form of PNT. $$\pi(x) = \frac{x}{\log x}+O\left(\frac x{(\log x)^2}\right).$$ We can write your sum as (apply partial summation) $$\int_{n/2}^n \frac{d\pi(t)}t = \frac{\pi(n)}{n} - \frac{\pi(n/2)}{n/2} + \int_{n/2}^n \frac{\pi(t)}{t^2} dt$$ Now, using the form of PNT ...

-1

Suppose not. (We take the negation of the theorem and suppose it to be true.) Suppose there are three cube roots who are in arithmetic progression although not necessarily consecutively. Let our radicands be the primes $p, q,$ and $r$ and the difference between terms in the arithmetic progression be $d$. $k_1$ and $k_2$ respectively represent the number of ...

2

If you want to eliminate multiples of 2 and 3, just work in base 6=2x3. The only possible primes are those that end in 1 or 5. Similarly, to sieve out numbers with all factors 2, 3, 5, and 7, work in base 2x3x5x7 = 210. This is standard stuff for those developing sieves, and there are many advanced takes on this. Read, play around, have fun, and don't ...

0

As you said, $k\cdot k^{-1} \equiv 1 \pmod p$. Therefore, whenever we have $k\cdot k^{-1}$ in a $\pmod p$ equation, we can replace it with $1$, since they are congruent in such a system. Here's an example: $$2x \equiv 3 \pmod{5}$$ Now, after doing some guess and check, you can find that $2\cdot 3 \equiv 1 \pmod 5$, meaning $2^{-1} \equiv 3 \pmod 5$. Notice ...

0

In the point you cannot see clearly, $n$ is the number of digits of $x^l$ and $m$ is the number of digits to the right of $b$. See at the following example explaining what happen: $$x^l=aabaaa=aa0000+b000+aaa$$ But $$aa0000=aaaaaa-aaaa=a(111111)-a(1111)\\b000=bbbb-bbb=b(1111)-b(111)\\aaa=a(111)$$ It follows $$x^l=a(111111)-a(1111)+b(1111)-b(111)+a(111)$$ $... 0 $$a\frac{10^n-1}{9}$$ is simply the number $$aaa\cdot\cdot\cdot aaa$$ with$n$digits$a$. To get$\ aaa\cdot\cdot\cdot b \cdot\cdot\cdot aaa\ $, you must add or subtract some multiple of a power of ten. 2 Well I don't think there is any "nice" closed form in the sense that you can evaluate it easily in term of standard functions. But you can write : $$n(p) = \pi(p)$$ Where$\pi(n)$is the Prime-counting function (Note that we have the famous result$x/ln(x) \sim \pi(x)$) 1 Here is something that I have established a long time ago. It illustrates the fact that one can easily establish such formula. The real challenge is to establish a formula which is not "computationally worthless". First, here is a formula which determines whether or not$x$is prime: $$f(x)=\left\lfloor\frac{\left(\sum\limits_{k=2}^{x-1}\left\lceil\... 1 With the prime factorization of n being$$n = \prod_p p^v$$we have$$\sum_{d|n} \lambda(d) = \prod_p \left(1 + (-1) + 1 + (-1) + \cdots + (-1)^v\right).$$Now if v is odd the corresponding factor is zero, so the sum is zero in this case as well. Therefore for this to be non-zero all v must be even. This yields the value one for the sum terms, ... 2 Define a b-tuple on (a_1,\dots,a_k) as [b_1,\dots,b_k] with 0\le b_i\le a_i,\;\forall 1\le i\le k. Then if a_i is odd, there are an even number of possibilities for b_i, and if a_i is even, there are an odd number of possibilities for b_i. So unless every a_i is even, i.e. n is a square, we have an even number of possible b-tuples, ... 3 If you put f(n)=\sum_{d|n} \lambda(d) and$$g(n)=\left\{ \begin{array}{c} 1 & \textrm{if$n$is square}\\ 0 & \textrm{otherwise} \end{array} \right. $$then you can see easily that if n,m are coprime :$$ f(nm)=f(n)f(m)\\ g(nm)=g(n)g(m) $$and$$ f(p^k)=g(p^k) \qquad \textrm{for all$p$prime number} $$so f=g 2 Your corrected conjecture is true. Suppose p is the smallest prime dividing n\in\mathbb N and suppose kn+ap=m!, where ap<kn, for some a,k,m\in\mathbb N, then there are k^{\prime},a^{\prime}\in\mathbb N such that k^{\prime}n+a^{\prime}p=(m+1)!, where a^{\prime}p<k^{\prime}n. Taking k'=(m+1)k and a'=a(m+1) works since$$k'n+... 1 Use the Euclidean algorithm on all$\frac{n(n-1)}{2}$pairs of$a_i$and$a_j$. If you get a GCD that is$F > 1$, then that is your answer. This is because$F \mid a_i$and$F \mid a_j$, so when you multiply them together, you get$F^2 \mid (a_ia_j)$, so$F^2 \mid X$. Euclidean algorithm runs in$O(\log a_i+\log a_j)$, so since$a_i \leq 10^{18}$, it ... 5 (Answering 1. only:) You have showed that the numbers$A_n$cannot be rational. But Mills' constant is the limit of that sequence of numbers, not one of the numbers themselves. There is nothing to prevent a sequence of irrational numbers from having a rational limit. For a simpler example, consider the sequence$c_n=2^{1/n}$, with$\lim_{n \to \infty} c_n=...

6

For $p=3$, $q$ has to be $2$. Suppose that there exist $k,m\in\mathbb Z$ such that $$3k+2=m!$$ Since $m\gt 2$, the RHS is divisible by $3$. This is a contradiction. Added : Similarly, for $p=5$, there is no such prime $q$.

2

For many people, using a good method such as BPSW (not a single Fermat test), is good enough. More importantly, the code for such a test is much simpler than good proof software, so in many cases it has more trust. A few example times with your number to give some idea. Your times will vary depending on software and computer. This is C+GMP. PFGW isn't ...

1

No matter how good the hardware is, you won't get a result that is better than what the algorithm gives, so if you're using an algorithm that detects probable primes and you want primes, you need to do something else, so (if this was supposed to be on topic at MSe) this comes down to the algorithms. If it's sufficiently fast to check whether a number is a ...

3

Use the fact that we have the following equivalences: $$p-1\mid pqg-1\iff p-1\mid qg-1$$ $$q-1\mid pqg-1\iff q-1\mid pg-1$$ $$g-1\mid pqg-1\iff g-1\mid pq-1$$ If $p>3$ is prime, $q=2p-1$ and $g=3p-2$ are also primes, then $3q=2g+1$. $q-1=2(p-1)$, so $2(p-1)\mid q-1$ and $q-1\mid 2(p-1)$. Also $g-1=3(p-1)$, so $g-1\mid 3(p-1)$. Also $p\equiv 1\pmod{3}... 1 a) Show that$p$divides both$n$and$\lfloor \sqrt n \rfloor!$b) Show that$p$does not divide both of$n$and$\lfloor \sqrt n \rfloor!$For the ultimate goal, if$n$is prime, then straight-forward calculation shows that$f(n) = 1$. On the other hand, if$n$is not prime, then it must be divisible by some prime$\leq \sqrt{n}$(why?), which means that$...

1

By definition of the prime counting function we have $\pi(p_n)=n$ for the $n$-th prime $p_n$. So, for $n\to \infty$, $$n=\pi(p_n)\sim \frac{p_n}{\log(p_n)},$$ which says $p_n\sim n\log(n)$.

0

One alternative way is to first prove that the number of primes $π(n)$ in the range $\{1\,..\,n-1\}$ is representable, and then "$x$ is the $n$-th prime" is represented by the formula: $π(x+1) = n \land π(x)+1 = n$. Since $π(0) = 0$ and $π(n+1) = π(n) + \mathbf{1}_{prime(n)}$ for any natural $n$, and since $prime$ can be represented by a $Δ_0$-formula, ...

2

Let's say $p$ divides $10^{2017}-1$. This means: $$10^{2017} \equiv 1 \pmod{p}$$ Using group theory, we know that $2017$ must be a multiple of the order of $10 \pmod p$. The order of $10 \pmod p$ is the smallest number $n$ such that $10^n \equiv 1 \pmod p$. We know that $n \neq 1$ because if $10^1 \equiv 1 \pmod p$, then $p=3$ or $p=9$. However, the only ...

9

You did not check quite far enough. $11^{3100}+3100^{11}$ $=2076462013023723087177998371272629862972883202603058638957413939624626$ $9054240698423859652025721171495403183350925185327797086492200207876487$ $2657520023839950330031205883217443601268748782180924528196277373392564$ $4013266704424018036520898747850451175736951267420442305614435735217327$ $... 5 This can be seen as a special case of the more general concept of valuations (on discrete valuation rings). A common notation in that context, which is quite convenient also here is$\nu_p(n)$. 6 Yes, there is a standard notation, namely$p^e\mid\mid n$, which says that$e$is the largest power of$p$which divides$n$. Reference: Martin Aigner, Number Theory. Edit: For more advanced purposes, like$p$-adic numbers etc., a common notation is also$\nu_p(n)$, which also then appears in more elementary context. For elementary number theory I have ... 0 Hint: Though it's tedious but the double integral is doable by subbing$u=1+x$then repeating integration by parts several times. You might use the following relation $$\operatorname{Li}_2(z)=\int_z^0\frac{\log(1-x)}{x}\ dx$$ 1 It seems the authors might have used (I admit that the numbers do not match completely) $$c=\frac{2e^\gamma}{3F_1(6)}\approx1.18787$$ (where$F_1$is also defined on page 7) instead of $$c=\frac{2e^\gamma}{3f_1(6)}\approx 0.82396$$ I don't have time or energy to understand which one is the correct one to put in the end. Mathematica calculates $$F_1(s)=\... 3 It seems like you miscopied the text in your question. It actually says that: An odd composite number 2n + 1 is in the sequence if and only if multiplicative order of 2 \pmod{(2n+1)} divides 2n. So Chandler's theorem states that, if 2^k \equiv 1 \pmod{(2n+1)}, then k | 2n. 4 Note that this Question deals with base 2 Fermat pseudoprimes rather than strong pseudoprimes as mentioned in one of the OP's earlier Questions. Carl Pomerance ("On the Distribution of Pseudoprimes", 1981) bounds the count P_2(x) of base 2 Fermat pseudoprimes less than x:$$ \exp\left\{ (\log x)^{5/14} \right\} \le P_2(x) \le x \cdot L(x)^{-1/2} $$... 3 Note that \phi(n) is even for all n\gt2. Consequently, if 2\lt m,n with \gcd(m,n)=1, then 4\mid\phi(mn), since \phi(mn)=\phi(m)\phi(n). Now 4\not\mid98, so \phi(N)=98 is possible only if N=p^r or 2p^r for some odd prime p. But \phi(2p^r)=\phi(p^r)=p^{r-1}(p-1)=98=2\cdot7^2 clearly has no solution, mainly because p=99 is not a ... 3 A prime factor p of N contributes a factor p-1 to \phi(N) and also a factor p^{e-1} if p^e divides N. Since 98 = 2 \cdot 7 \cdot 7, consider where 7 comes from. It cannot come from p=7, because 6 does not divide 98. It cannot come from p-1, because 8 is not prime. It must come from a factor of p-1. The two factors of 7 in ... 3 Clearly N\ge 2. If N=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n} is the unique prime factorization of N (with p_1<p_2<\cdots <p_n), then$$\phi(N)=p_1^{\alpha_1-1}p_2^{\alpha_2-1}\cdots p_n^{\alpha_n-1}\times\times (p_1-1)(p_2-1)\cdots (p_n-1)=2\cdot 7^2$$If N is even, then p_1=2 and$$2^{\alpha_1-1}p_2^{\alpha_2-1}\cdots ... 2 For any given definition of natural numbers the existence of prime numbers is a matter of fact. Obviously the property that characterize these numbers is a consequence of the definition of the binary operation called ''multiplication''. In some sense we can consider the existence of the prime numbers a consequence of the existence of commutative rings ... -3 This is such an interesting question! I am not an expert, I've only taken a introductory course on number theory, however what I've always thought is that the reason for prime numbers to exist, is the same as for atoms to exist. I mean, we know atoms are not the ultimate 'brick' of matter, however stick with it. The atoms bonded together form everything ... 0 (1),(2): Correct, but you didn't prove (2). If you claim that$Im_f(S)$is a set$T$, then you must show that indeed$f$maps everything in$S$into$T$, and conversely everything in$T$is the image of something in$S$under$f$. (3): You have the right idea for minimum and maximum, but your reasoning is totally flawed for minimal and maximal. Minimal ... 2 A part of this information is on page 36 in the first edition of Cox. Then the table on page 60. Still, takes a bit of digging to find all this. Other than$2,3,7,$the primes in question are $$1, 5, 11, 17, 19, 23, 25, 31, 37, 41, 55, 71 \pmod {84}$$ All of them can be written in one of four ways, $$p = x^2 + 21 y^2,$$ $$p = 2 x^2 + 2 x y + 11 y^2, ... 3 Let p be an odd prime not equal to 7. If p\equiv 1\pmod{4}, then (7/p)=(p/7). But (p/7)=1 if p\equiv 1,2,4\pmod{7}. That gives, modulo 28, p\equiv 1, 9, 25. If p\equiv 3\pmod{4}, then (7/p)=-(p/7). But (p/7)=-1 if p\equiv 3,5,6\pmod{7}. That gives, modulo 28, p\equiv 3, 19, 27. Now we can write down the 6 congruence classes ... 1 The tuple (x, 4x+1) is an admissible 2-tuple in the language of the k-tuples conjecture of the conjectures of Hardy and Littlewood. It is believed that there are infinitely many x such that x and 4x+1 are simultaneously prime. More generally, given an admissible k-tuple, it is beleived that there are infinitely many x such that all k ... 0 I have understood the solution. The solution can be produced by using integral equation : e0 + e1+ e2+ ....+ el = t. 2 Yes. The sum of the coefficients of a polynomial is just the polynomial evaluated at 1. So since the value of the interpolation at 1 is p_1=2, the sum of the coefficients will always be 2. To see this, just consider: If$$p(x)=\sum_{i=0}^n a_ix^i,$$then$$p(1)=\sum_{i=0}^n a_i(1)^i=\sum_{i=0}^n a_i.$$0 Hope this helps with regards to whether it was previously found: 2 and 3 might be referred to as the two "forcibly prime numbers" since there are no integers greater than 1 and less than or equal to their respective square roots. Not a single trial division ever needs to be done for 2 or 3, so they are disqualified from the outset from any attempt to belong ... 3 This is a question that is going to get lots of duplicates. That's how I came across it. Let me answer your question with another question: Is -14 prime? Of course it isn't! Since$$\frac{-14}{2} = -7,$$for starters. It is also divisible by -7, -2, 7, as well as by its obvious divisors, -1, 1, 14 and itself. Clearly -14 is a composite number.... 4 Collecting my results together, there is a 7-length sequence found for 7: 7, 157, 307, 457, 607, 757, 907 Note that, starting at 11 (or larger prime), to have a sequence of length 7 or more it is essential that the step is divisible by 7\#=210, to avoid multiples of the lesser primes, and in general for the p-length sequence from ... 1 "Strictly" means that 1 and √n are not included. For example, 3 is between 1 and 3 but is not strictly between 1 and 3 It relates to this statement because it's excluding the case where they are equal. 2 I won't comment on your technique, rather an obvious solution that means I can look at these and tell you they aren't prime. An odd number multiplied by an odd number is always odd - namely a power of an odd number is odd - so 2015^7 is odd and so 2015^7 - 1 is even, and thus not prime (2 is the only even prime). Similarly 817^2 and 53^2 are both odd, ... 2 First of all,$$9^{47^{51}}=3^{2\cdot47^{51}}$$As \phi(67)=\lambda(67)=66,$$3^{2\cdot47^{51}}\equiv3^{2\cdot47^{51}\pmod{66}}\pmod{67}$$As (2\cdot47^{51},66)=2, let us find 47^{51}\pmod{33} As \lambda(33)=\cdots=10,51\equiv1\pmod{10},$$47^{51}\equiv47^1\pmod{33}\equiv14\implies2\cdot47^{51}\equiv14\cdot2\pmod{66}\implies3^{2\... 2 $$\phi(67)=66=2\cdot 3\cdot 11$$ and By Fermat's Theorem, $$47^{51}\equiv47^{1}\equiv 47\pmod2$$ $$47^{51}\equiv47^{1}\equiv 47\pmod3$$ $$47^{51}\equiv47^{1}\equiv 47\pmod {11}$$ Thus, using Chinese Remainder $$47^{51}\equiv 47\pmod {66}$$ Thus, by Fermat' Little theorem:$$9^{47^{51}}\equiv 9^{47}\equiv 3^{94}\equiv 3^{28}\equiv (-64)^{28}\equiv ((-4)^... 2 First focus on$47^{51}$in your example. You must figure that out mod$66$, the latter number being the Euler totient of$67$. Let$r$be that residue and then attack$9^r$modulo$67\$.

Top 50 recent answers are included