# Tag Info

1

(I've completely rewritten this answer, to make it closer to that of the given solution.) Let us consider such positive integers separately, by their remainder modulo $42$. So fix an $r$, where $1 \le r \le 42$. (We're picking $1 \le r \le 42$ instead of the conventional $0 \le r < 42$, because we only care about positive numbers and this makes some ...

0

At every step, the number of characters copied to be pasted then an arbitrary number of times has to be a divisor of $n$(because no matter how many times we paste them then, the resulting amount of characters will be a multiple of the number of characters we copied). So let $\xrightarrow{a}$ mean that I copy the characters in the buffer and then I paste them ...

2

Let P(i) denotes the i-th prime number, then when n is between P(i) and P(i+1)-1, $\pi$(n) doesn't change. Group these terms with the same sign together, we obtain a new series: $\sum \hat{a}(k)$. Now we have an alternating series. we use the Leibniz's theorem: "If the absolute value of $\hat{a}(k)$ decreases with k, and $\lim_{n\to\infty}\hat{a}(k)=0$ ...

4

Theorem $\$ The polynomial $\rm\ f(x)\ =\ (x\!-\!\alpha)\,(x\!-\!\alpha')\ =\ x^2 + x + k\$ assumes only prime values for $\rm\ 0\ \le\ x\ \le\ k-2 \ \iff\ \mathbb Z[\alpha]\$ is a PID. Hint $\ (\Rightarrow)\$ Show all primes $\rm\ p \le \sqrt{n},\; n = 1-4k\$ satisfy $\rm\ (n/p) = -1\$ so no primes split/ramify. For proofs, see e.g. Cohn, Advanced ...

4

Since $4(n^2+n+41)=(2n+1)^2+163$, one way would be to methodically show that $-163$ is a quadratic non-residue mod all (odd) primes less than $41$. Added later: The OP has asked for further details, so here goes. If $p\mid n^2+n+41$, then $(2n+1)^2+163\equiv0$ mod $p$, which means that $-163$ is a square mod $p$. Now the values of $n^2+n+41$ for $n\lt40$ ...

5

We will prove this using the PID $R:=\mathbb{Z}[\omega]$, where $\omega=\frac{1+i\sqrt{163}}{2}$, with the norm $N(a+b\omega)=|a+b\omega|^2=a^2+ab+41b^2$. Lemma 1: If $p$ is prime in $\mathbb{Z}$ such that $\exists n\in\mathbb{Z}$ such that $p|n^2+n+41$, then $p$ is reducible in $R$. Proof: Let $p|n^2+n+41$ and assume $p$ is irreducible. Then $p$ is also ...

6

Every odd prime has this property - even if you replace $p^2$ by $p^k$. (pretty awesome, huh) Find a solution $(x_1,y_1)$ to $x_1^2+y_1^2+1\equiv0\pmod p$; without loss of generality, $p$ doesn't divide $x_1$. Consider the polynomial $x^2+(y_1^2+1)$. This polynomial has a root $x_0$ modulo $p$, and its derivative at that root is $2x_0\not\equiv0\pmod p$. ...

1

So with $c = e/\pi$ you're plotting $[n^c, y]$ whenever $p_y$ divides $n$, where $p_y$ is the $y$'th prime. The $k$'th curve from the top comes from the points where $n = k p$ where $p$ is prime (i.e. in the top curve $n$ is prime, in the second it's twice a prime, etc). Thus this is a plot of $[n^c, \pi(n/k)]$ where $\pi(x)$ is the number of primes $\le ... 2 A book I recommend for this material is Duncan A. Buell, Binary Quadratic Forms and USED COPIES. This discriminant has class number two. This form is alone in its genus. Also, the principal form represents$-1,$so there is no distinction between representing$p$and$-p.$This form represents$37$and$113$and all primes that are nonresidues$\pmod {37}$... 0$2^5\lt49\lt2^6$;$2^{49}-1$is divisible by the prime$p=4432676798593$;$p-1$is$2^7$times an odd number; so if I follow your definitions,$i=1$. 1 You can stipulate the leading decimal digits of a number$n$by setting limits on the fractional part of$\log_{10}n$. For instance, the leading digits of$n$are$142857$if$\lfloor\log_{10}142857\rfloor \le \lfloor\log_{10}n\rfloor < \lfloor\log_{10}142858\rfloor$To find an integer$k$such that the leading digits of$2^k$are$142857$, we want ... 5 There is undoubtedly a nicer answer, but here goes. Note that$3\cdot 2+(-1)\cdot 5=1$. Because it looks nicer, let$a=3$and$b=-1$. Consider$(2a+5b)^{2n-1}$, and expand using the Binomial Theorem. Then the first$n$terms will be divisible by$2^n$, and the last$n$will be divisible by$5^n$. That gives us the desired linear combination. Explicitly, ... 2 This answer will use some slightly more advanced machinery to get a short answer. If$n\geq 3$(you don't need to assume$n > 3$) then$-1\neq 1$in$\mathbb{Z}/n\mathbb{Z}$, but$(-1)^2 = 1$, so$-1$is an element of order$2$in$(\mathbb{Z}/n\mathbb{Z})^{\times}$, which means that$|(\mathbb{Z}/n\mathbb{Z})^{\times}| = \varphi(n)$is even by Lagrange. ... 2 Hint$\ $The map$\,x\mapsto -x\pmod n\,$has no fixed points so pairs-up the residues coprime to$n.\,$Remark$\ $Such use of reflections (or involutions) to pair-up terms frequently proves handy, e.g. see prior posts here on Wilson's theorem (in groups), esp. this one to start. 1 If$t$is chosen randomly (uniformly) from a large enough interval,$p_n^{it}$for different$n$should be good approximations to independent random variables with uniform distribution on the unit circle. This distribution has mean$0$and covariance matrix$\pmatrix{1/2 & 0\cr 0 & 1/2\cr}$. The sum, for large$k$, has approximately a bivariate ... 20 You can do it via the formula as you do, but you can also simply use the definition that$\phi(n)$is the number of numbers$k$, with$1 \le k \le n$, such that$\gcd(n, k) = 1$. Clearly, if$\gcd(k, n) = 1$, then$\gcd(n - k, n) = 1$as well, so (for$n > 2$) all the numbers relatively prime to$n$can be matched up into pairs$\{k, n-k\}$. So ... 8 Suppose$n>3$. If$n$has an odd prime factor, say$p$; then$n=p^km,(m,p)=1$and$\varphi (n)=\varphi(p^k)\varphi(m)=(p-1)p^{k-1}\varphi(m)$, with$p-1$even. If$n$has no odd prime factors, then$n=2^k$with$k>1$so$\varphi(2^k)=2^{k-1}$is even. 2 Here is a group action proof. Let$G$be a cyclic group of order$p^km$and let$H$be the subgroup of$G$of order$p^k$. Let$H$act on the set$X$of subsets of$G$of size$p^k$. Then since$H$is a$p$-group, the number of fixed points of$H$on$X$is congruent to the size of$X$modulo$p$. But a subset of size$p^k$is fixed by$H$iff it is a ... 2 Any linearly recursive integer sequence has the property that every large enough prime divides some term, as long as some term of the sequence is equal to$0$. That follows from the solution of linear recursive sequences. Number the sequence so that$S_0 = 0$, and consider primes$p$not dividing any of the denominators or characteristic roots that ... 0 Finding an$x$that violates the given inequality is only one way to disprove the Riemann Hypothesis. Another way would simply be to find a (nontrivial) zero of the zeta function with real part not equal to$1/2$. So far we've "only" computed about ten trillion zeros. The first counterexample could be the very next one. 0 Probably the Riemann Hypothesis is true, in which case its falsity would not be provable (and the believability of its falsity is more a matter of psychology than mathematics), whether by computation or otherwise. 1 No, because we can extend the proof to show that there are numbers divisible by 3, 5, etc. In fact, for any choice of$w\in\mathbb{Z}^+,$there are infinitely many numbers in the generated sequence which are divisible by any given$w$. 0 Since$500 \equiv 4 \mod 8$whereas$18 \equiv 2 \mod 8$, the number of stamps of$18$cents should be$2 \mod 4$(it should be even to make the result divisible by$4$, it cannot be divisible by$4$to make sure the result is not divisible by$8$). Suppose we use$4k+2$of these stamps, having a total value of$72k+36$. Then we use$(500-72k-36)/8 = 58-9k$... 0 If$a\ge1$then$[p_n,2p_n]\subseteq[ap_n,(a+1)p_n]$so it suffices to consider$[p_n,2p_n]$. But$(p_n,2p_n)$contains a prime by Bertrand's postulate, and such a prime cannot be divisible by$p_n$or any smaller prime. 1 Well, any positive integer$\ge 1$can be written as the product of primes, like $$n = p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3}\cdot ... p_n^{e_n} = \prod_{i=0}^n p_i^{e_i}$$ so, all the divisors of$n$are all the possible values of$p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3}\cdot ... p_n^{e_n}$, which are evidently $$(e_1+1)\cdot (e_2+1)\cdot (e_3+1) ... ... 2 If n=p_1^{k_1} \cdots p_r^{k_r} is the prime factorization of n then n has d divisors where$$d=(k_1+1)(k_2+1)\cdots (k_r+1).$$Thus you need to take the goal number of divisors and factor it in all ways as a product of one or more factors each greater than 1. This means for example in case (d) where you want 4 divisors, the possibilities are (4) ... 0 I think you are needing to work with modulo arithmetic. The term inverse though can mean a few things. Explanation below. Additive inverse: a+(-a)=0 here we have that -a is the additive inverse of a. I don't think you are interested in additive inverses here. Additive inverses mod n are from the group \mathbb{Z}_n=\{0,1,2,...,n-1\}. Multiplicative ... 1 Hint: Chinese Remainder Theorem. We want i (i+1) \equiv 0 \pmod{p}. What does that tell you about i \pmod{p}? How about i \pmod{q}? And hence, why are there 4 solutions? 1 Here's my attempt to flesh out of Charles's answer to enhance my own confidence and understanding. For convenience, I'm going to define \ell(x) = x\ln x: First of all, note that \ell(x+1)-\ell(x) = \ln(x+1)+x\ln(x+1)-x\ln x =\ln(x+1)+x\left(\ln(x+1)-\ln(x)\right) = \ln(x+1)+x\ln(1+\frac1x). More broadly, \ell(x+m)-\ell(x) ... 2 It sounds like you are working in modular arithmetic. So for 5 you are supposed to find x=\frac 11 \pmod 5, y=\frac 12 \pmod 5, etc. x is pretty easy. For y, you need to find z such that 2z=1 \pmod 5, and so on. 1 Make it an answer...there is no easy solution for this. p=2 works but p=5 fails. Other than those, -1 needs to be a quadratic residue, so p \equiv 1 \pmod 4 is a requirement. However, this is not always enough, as p=41 fails. jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus ./Pell Input n for Pell 205 0 form 1 28 -9 delta -3 1 form ... 2 No. For any choice of k>0 there is some n>1 such that \lfloor kn\log n\rfloor is even (and greater than 2). Consider kn\log n\bmod1. 1 You are looking at a four-dimensional analogue of the famous "Erdös multiplication table problem". In that problem, we want to know N_2(x), the number of distinct integers occur in the form mn where 1\le m\le x and 1\le n\le x. Clearly N_2(x) is less than x^2; Erdös was the first to show that N_2(x)/x^2 tends to 0 as x tends to infinity. A ... 1 Numbers expressible as p^3 + q^3 with p, q prime in at least two ways at the Online Encyclopedia of Integer Sequences has many examples, the smallest being$$6058655748 = 61^3 + 1823^3 = 1049^3 + 1699^3$$So this means$${1823^3-1699^3\over1049^3-61^3}=1$$This at any rate answers a question raised in the comments. 0 The simple computer route to this is to do four nested loops. You can require that each number be at least as large as the one before, which gives somewhat more than \frac 1{4!}100^4 \approx 4,200,000 products (the divisor is smaller when there are duplicates), then sort the products and throw out duplicates. I suspect it is rather close to 4E6 because ... 0 One solution: Use this. Otherwise, what you need to prove is that$$ n_1 \mid d \text{ and } n_2 \mid d \implies \text{lcm}(n_1,n_2)\mid d $$How you would go about doing this depends on how you define (i.e. how your textbook defines) \text{lcm}(n_1,n_2) 2 They're called truncatable primes. For a list of them on OEIS, see A024785, A020994, A055521 7 This is problem 5 from day 1 of the 2013 IMC. See here for one solution, and the official solution. 8 We can in fact show a stronger statement with some algebraic number theory: If p>5 is prime then p|F_{p\pm 1} for some choice of + or -. Suppose \left(\frac{5}{p}\right)=1. In this case, p splits in \mathbf{Z}\left[\frac{1+\sqrt{5}}{2}\right]=\mathbf{Z}[\varphi]. Thus, we can write p=\pm\pi\bar\pi, where \pi and \bar\pi are conjugate ... 8 The trivial answer is: yes F_0=0 is a multiple of any prime (or indeed natural) number. But this can be extended to answer your real question: does this also happen (for given~p) for some F_n with n>0. Indeed, the first coefficient (the one of F_{n-2}, which is 1) of the Fibonacci recurrence is obviously invertible modulo any prime~p, which ... 56 Yes. Consider any prime p. (Actually we don't need p to be prime; consider any nonzero number p.) You can of course take F_0 = 0 which is divisible by p, but let's suppose you want some n > 1 such that F_n is divisible by p. Consider the Fibonacci sequence modulo p; call it F'. That is, you have F'_0 = 0, F'_1 = 1, and for n \ge ... 19 According to the Wikipedia article on Fibonacci numbers if p is a prime number then$$F_{p - \left(\frac{p}{5}\right)} \equiv 0 \text{ (mod } p) $$where \left(\frac{p}{5}\right) is the Legendre symbol.$$\left(\frac{p}{5}\right) = \begin{cases} 0 & \textrm{if}\;p =5\\ 1 &\textrm{if}\;p \equiv \pm1 \pmod 5\\ -1 &\textrm{if}\;p \equiv \pm2 ... 0 "Numerical Methods in Economics" by Kenneth L. Judd gives the construction as Weyl:$x_n=(\{n\sqrt{p_1}\},...,\{n\sqrt{p_d}\})$Haber:$x_n=\left(\left\{\tfrac{n(n+1)}2\sqrt{p_1}\right\},...,\left\{\tfrac{n(n+1)}2\sqrt{p_d}\right\}\right)$Niederreiter: ... 3 Hint: There is an infinite number of primes of the form$4N -1$. Proof: By contradiction. Suppose not. Let the primes of the form$4N-1$be$p_1, p_2, \ldots p_k$. Consider the number $$A = 4 p_1 p_2 \ldots p_k - 1.$$ Hint: Show that there must be a prime of the form$4N-1$that divides$A$. 4 Define$\Omega(n)$by the number of all prime divisors of$n$counted with multiplicity, and$\omega(n)$by the number of distinct prime divisors of$n$. Then the average that you are interested is$\Omega(n)/\omega(n)$. This function has lower limit$1$since for$n=p$prime, we have$\omega(p)=1$,$\Omega(p)=1$. On the other hand, this has upper limit ... 3 They are generated on the machine doing the encryption. Generating primes of a given size is fairly easy, and verifying that they are prime can be done much faster than trial division. 1024-bit RSA requires two 512-bit primes. On my (old) machine it takes about 34 milliseconds to generate a 512-bit prime (so generating the whole key would take about 0.07 ... 1 Your problem is a special case of the solution of a system of congruences that is encapsulated in the fundamental Chinese Remainder Theorem (CRT), which applies in this case since the moduli$\,p_i$are pairwise coprime, being distinct primes. See the linked Wikipedia article for the basics and please feel free to ask for further elaboration if anything ... 4 For real sequences, this is impossible. If the series converges for any even exponent$m$, then$a_n\rightarrow 0$as$n\rightarrow\infty$, and hence$|a_n|^{m'} < |a_n|^{m}$for sufficiently large$n$and any$m'>m$. Therefore, if the series converges for any even exponent, it is absolutely convergent for all larger exponents. (In particular, if it ... 2 That can't exist for positive$a_n$at least. Take primes$p$and$q$, and a composite$m$such that$p < m < q$. Then if$\sum a_n^q$converges, by the comparison test$\sum a_n^m$converges too. It looks to me that this should work for all$a_n\$, but I don't see how to prove it offhand.

Top 50 recent answers are included