# Tag Info

## New answers tagged number-theory

1

Defining $$g(x):=10\uparrow^{x-1}100,$$ we have $$\mathrm{googolplum} =g^N(2) ,$$ where $$N = (10^{100})\uparrow^{3^{27}-2} (10^{100}).$$ Here's a proof (sketch) that $$f_{\omega+2}(2) < \mathrm{googolplum} < f_{\omega+2}(3)\tag{*}.$$ For the inequality on the left in $(*)$: $$f_{\omega+2}(2) = f_{\omega+1}^2(2) = f_{\omega+1}(a) = ... 0 Hint : If a and b are coprime, then there is no prime p dividing both a and b. Consider the prime factors of a\cdot b and locate the corresponding factors of \phi(a\cdot b) (they either belong to \phi(a) or to \phi(b)) 1 We are looking for integers k>1 with gcd(3^{k-1}+1,k)=1. Clearly k has to be odd, because otherwise both numbers are even, so that its gcd is divisible by 2. For odd primes k we have 3^{k-1}\equiv 1 \bmod k so that gcd(3^{k-1}+1,k)=1. Now try to extend this to all odd k>1. 2 A number n satisfys 2^n\equiv 1\ (\ mod\ (n+1)\ )\ , if and only if n+1 is a fermat-pseudoprime to base 2. In particular, if n+1 is an odd prime, the congruence holds. But it can also hold, if n+1 is composite, the smallest example is n=2046. Note , that there are infinite many composite fermat-pseudo-primes to base 2. Another way to ... 2 Hint: Use Fermat's_little_theorem and Fermat_pseudoprime Let n=p-1, where p - prime. Then$$2^{p-1}\equiv1 (\bmod p)$$Let n=p-1, where p- composite number. Then p \in  A001567 4 At first glance, your proof is probably wrong simply because it is too simple. It really does look like you are missing something. Sure, there exists simple proofs, but it should immediatelly raise an alarm as they aren't that common, especially as-yet-undiscovered very simple proofs of complex theorems. A deeper inspection reveals your mistake: You ... 0 Obviously b>c. Multiply both sides by abc to get$$bc+ac=ab$$It follows immediately that$$a=\frac{bc}{b-c}=\frac{bc-c^2+c^2}{b-c}=c+\frac{c^2}{b-c}$$So b-c|c^2, but \gcd(b-c, c^2)=1 since \gcd(b, c)=1. Hence we must have b-c=1, which in turn gives a=c+c^2. From c+c^2=a<22 one gets c<5, so c=4 and thus the only solutions is$$(a, ...

0

$1/a + 1/b = 1/c$ so $1/a =1/c - 1/b$ so $a = 1/[1/c-1/b] = bc/(b-c)$ As this is a whole number $b-c$ divides $bc.$ So any factor of $b-c$ must be a factor of either $b$ or $c.$ If it's a factor of $b$ and also $b-c$ it is a factor of $c$ as well. If is a factor of $c$ and also $b-c$ then it is also a factor of $b.$ Either way, any factor of $b-c$ is a ...

-1

As you say, $a,b \gt c$. Presumably you demand $a \neq b$ or there would be many solutions with $a=b=c/2$. We can demand $a \gt b$ and just try values for $b-c$. If $b-c=1$, we have $a=c+c^2$ and the only value in range is $c=4, a=20, b=5$. If $b-c=2,$ we must have $c$ even and $a=c+c^2/2$, which works with $c=4, a=12, b=6$, but $c=6$ makes $a$ too ...

0

Let $p$ prime $p|(b-c)$ and $p|c^2$. From $p|c^2$ we get $p|c$ then $p|b$ because $b=(b-c) + c$. Now let $p$ prime $p|b, p|c$. It follows that $p|(b-c), p|c^2$. The conclusion is $\gcd(b,c)$ and $\gcd(b-c,c^2)$ have the same prime divisors. From here we deduce if one of them is $1$ the other one is also $1$. Back to your problem. Because $\gcd(b,c)=1$, we ...

0

Then equation: $$XY+XZ+YZ=N$$ If we ask what ever number: $p$ That the following sum can always be factored: $p^2+N=ks$ Solutions can be written. $$X=p$$ $$Y=s-p$$ $$Z=k-p$$

0

Dirichlet's unit theorem explicitly states that if $|\cdot |_1, \ldots, |\cdot |_r$ are the real absolute values and $|\cdot |_{r+1},\ldots, |\cdot|_{r+s}$ are the complex ones, then the log map $$l:\begin{cases}\mathcal{O}_K\to \Bbb R^{r+s} \\ l(\alpha) = (\log |\alpha|_1,\ldots , \log |\alpha|_r, \log|\alpha|_{r+1},\ldots, \log ... 1 Obviously b>c. Multiply both sides by abc to get$$bc+ac=ab$$It follows immediately that$$a=\frac{bc}{b-c}=\frac{bc-c^2+c^2}{b-c}=c+\frac{c^2}{b-c}$$So b-c|c^2, but \gcd(b-c, c^2)=1 since \gcd(b, c)=1. Hence we must have b-c=1, which in turn gives a=c+c^2. From c+c^2=a<22 one gets c<5, so c=4 and thus the only solutions is$$(a, ...

1

Remember that $\left({\cdot\over\cdot}\right)$ is a homomorphism from $\Bbb Z/p\Bbb Z^\times$ to the group $\{\pm 1\}$. But then the kernel has size ${p-1\over 2}$ by Lagrange's theorem. Then the other half of the elements map to $-1$. So you have exactly ${p-1\over 2}$ $+1$s and the same number of $-1$s, so they all cancel out in the sum. In your case, you ...

2

Hint: Do you know that $\left(\dfrac{ab}{p}\right)=\left(\dfrac{a}{p}\right)\left(\dfrac{b}{p}\right)$ for $a,b$ prime to $p?$ Also, can you show that $d$ is even?

0

To answer your second question, a general fact from group theory, known as Lagrange's theorem, implies that the order of every element divides the size of the group, which in this case is $p-1$.

0

If carry is not allowed, better bound would be $5* 9^{\lceil log_{10}^n\rceil - 1}$ + some delta. But, what happens when carry is there in addition?

4

This has no chance of even being remotely true. Let $a=2$ and let $x$ be an odd integer. Then $\gcd(a,x)=1$ and $\varphi(a)=1$ and $a\mid x^n-1$ for any $n>0$, so certainly $n\nmid\varphi(a)$. More generally, if $n\mid m$ then $x^n-1\mid x^m-1$, so if $a\mid x^n-1$ then there exist arbitrarily large $m$ such that $a\mid x^m-1$. So we certainly can't ...

3

Substituting the first in the second gives $$x^3+y^3+(x+y)^2-2(x+y)=0$$ so $x+y=0$ (giving $z=1$) or $$x^2-xy+y^2+x+y-2=0,$$ that is, $$\left(x+\frac12-\frac y2\right)^2+\frac34(y+1)^2-3=0$$ so $(y+1)^2\leq4$, which leaves to check $y\in\{-3,-2,-1,0,1\}$. All solutions are given by \begin{align*}(x,y,z)\in\{&(a,-a),\;a\in\mathbb Z,&&(z=1)\\ ... 1y=-x, z=1{y = \frac{-1 + x - \sqrt{3} \sqrt{3 - 2 x - x^2}}{2}, z = \frac{3 - 3 x + \sqrt{3} \sqrt{3 - 2 x - x^2}}2}{y = \frac{-1 + x + \sqrt{3} \sqrt{3 - 2 x - x^2}}{2}, z = \frac{3 - 3 x - \sqrt{3} \sqrt{3 - 2 x - x^2}}2}$$All integer solutions: x=-3, y=-2, z=6 x=-2, y=-3, z=6 x=-2, y=0, z=3 x=0, y=-2, z=3 x=0, ... 5 A general identity that is nice to know is$$x^3+y^3=(x+y)(x^2-xy+y^2).$$Given that x+y=1-z and x^3+y^3=1-z^2 we have z=1-x-y and hence$$x^3+y^3=1-z^2=(1-z)(1+z)=(x+y)(2-x-y).$$This means that either x+y=0, so y=-x and z=1, or$$x^2-xy+y^2=2-x-y.$$This is a quadratic in x, and quadratics are easy. Applying the quadratic formula yields ... -1 x=1, y=0, and z=0. or x=0, y=1, and z=0.and many more solution possible. 2 By the Jensen's inequality,$$ \log[a^ab^b]=a\log a+b\log b\leq\log[a^2+b^2]\implies a^ab^b\leq a^2+b^2. $$Similarly,$$ \log[a^bb^a]=a\log b+b\log a\leq \log[ab+ba]\implies a^bb^a\leq 2ab. $$Summing then gives:$$ a^ab^b+a^bb^a\leq a^2+b^2+2ab=(a+b)^2=1. $$2 The gcd condition that MXYMXY stated is the most general possible. Your equations imply that that x^{b\pm a} \equiv 1 \pmod p, which happens if and only if \mathrm{ord}(x)\mid b\pm a. This, of course is equivalent to \mathrm{ord}(x) \mid a and \mathrm{ord}(x)\mid b, which is in turn equivalent to \mathrm{ord}(x)\mid \gcd(a,b). 0 1=(a+b)^2=a^2+b^2+2ab\ge a^a\cdot b^b + a^b\cdot b^a using Jensen's inequality on a^2+b^2 and 2ab. 2 Hint: Since a + b = 1, we can use the Weighted Arithmetic Mean - Geometric Mean inequality to get$$\sqrt[a+b]{a^a b^b} \leq a^2 + b^2.$$Similarly, write the inequality for the other term to get the desired result. 2 You can also do it solving the two equations for b and c to be expressed as functions of a. This would give$$b=\frac{12}{5}-\frac{13 a}{5}\qquad c=\frac{13}{5}-\frac{12 a}{5}Now, replace in the expression, expand and simplify. 8 Given a + 8c= 7b + 4 and 8a - c = -4b + 7 Now Squaring both equation, We get \begin{align}a^2 + 64c^2 + 16ac&=49b^2 + 16 + 56b\tag{1} \\ 64a^2 + c^2 - 16ac&=16b^2 + 49 - 56b\tag{2}\end{align} Summing these two equations gives 65a^2 + 65c^2 = 65b^2 + 65 \Rightarrow a^2 - b^2 + c^2 = 1 $$3 It is not true. 3\cdot 4=12 \equiv 0 \pmod 4 1 Assume the prime factorization of n is n=p_1p_2\dots p_r. Let U=\{1,2,\dots, r\} and V=\{1\leqslant i\leqslant r|\gcd (x,p_i)=1\}. Then U-V=\{1\leqslant i\leqslant r,p_i|X\}. So, we divide U into two disjoint parts. If V=\emptyset, then we can check the period t=1, since x^m\equiv 0(\mod n) for all m\in\mathbb{Z}_{>0}. If V\neq ... 1 The triples that satisfy your condition are of two types. Type 1 are the triples with smallest element 0, and Type 2 are the ones with smallest element \ge 1. There are just as many triples of Type 1 with sum n as there are pairs (y,x) with 0\le y\le x such that y+x=n. There are just as many triples of Type 2 with sum n as there are triples ... 2 Note that for any three positive integers a,b,c, if 2^k\leqslant b<a<c<2^{k+1} for some k\in\mathbb{Z}_{>0}, then$$bc<ac<a\cdot 2^{k+1}=2a\cdot 2^k\leqslant 2a\cdot a=2a^2,$$and$$bc>ba\geqslant 2^ka=\frac{1}{2}\cdot 2^{k+1}a>\frac{1}{2}\cdot a\cdot a=\frac{1}{2}a^2.$$Thus, 2^k\leqslant b<a<c<2^{k+1} for some ... 2 This is hopeless. For example, we can build a set E of density 1/2, such that \pi E will not have density 1/2, as follows: I'm going to include one half of the numbers in N^2\le n<(N+1)^2 in E, for each N\ge 1. Then E will have density 1/2, and for this it does not matter which numbers exactly I choose. Summary: The exact procedure is a ... 1 Let set S be the set of integers from 1 to 2046, we split S to S_is like this:$$S_1=\{1,2,3\}\\S_i=\{s\in\mathbb{Z}\,|\,2^{i}\le s\lt2^{i+1}\}\quad (2\le i\lt10)\\ S_{10}=\{1024,1025,\dots,2046\}$$So we have 10 sets in total, by Pigeonhole principle there's a set which has at least \lceil\frac{21}{10}\rceil=3 elements from those 21 chosen ... 6 Let the 21 numbers be x_1<x_2<\ldots <x_{21}. It is not possible to have x_{k+2}\ge 2x_k+1 (or equivalently x_{k+2}+1\ge 2(x_k+1)) for all k as that would lead to 2047 \ge x_{21}+1\ge 2^{10}(x_1+1)\ge 2^{11}=2048. Thus we find k such that x_{k+2}\le 2x_k. With b:=x_k, a:=x_{k+1}, c:=x_{k+2}\le 2b, we have$$ bc\le ...

1

You can deliberately define an irrational number to have this non-repeating quality, if required. For example, for an irrational number that avoids 3-blocks of repeating digits, take the binary definition of $\pi$ and generate a new number such that each digit $x$ in $\pi$ is replaced by $11x00$. (This also avoids 4-blocks). To avoid any repetitions of ...

7

Let $a=z$, $b=y-z$, $c=x-y$. We are looking for the number of solutions of $c+2b+3a=n$ with $a,b,c\geq 0$, so the answer is given by: $$[x^n](1+x+x^2+x^3+\ldots)(1+x^2+x^4+x^6+\ldots)(1+x^3+x^6+x^9+\ldots)$$ i.e. by: $$[x^n]\frac{1}{(1-x)(1-x^2)(1-x^3)} \tag{1}$$ that can be recovered through partial fraction decomposition. The meromorphic function ...

0

$${{\left( {{\left( b\pm\sqrt{2{{b}^{2}}-1}\right) }^{2}}-{{b}^{2}}\right) }^{2}}+4{{b}^{2}}\,{{\left( b\pm\sqrt{2{{b}^{2}}-1}\right) }^{2}}={{\left( {{\left( b\pm\sqrt{2{{b}^{2}}-1}\right) }^{2}}+{{b}^{2}}\right) }^{2}}$$ $${{b}_{n}}=\sum_{k=0}^{n}{\left. {{2}^{k+\operatorname{floor}\left( \frac{k}{2}\right) }}\,{{3}^{n-k}}\,\begin{pmatrix}n\\ ... 4 Use induction. Check the base cases. Let's look at the partitions of 2n+1. Every partition of 2n+1 includes odd number of 1s. If a partition contains 2k+1 1s, all the other terms in it are even. This kind of partitions can be identified with partitions of n-k by dividing the even numbers by 2. So, q(2n+1)=q(n)+q(n-1)+\ldots+q(2)+q(1)+1, ... 0 You already seem know that the norm of a prinicipal ideal is the norm of its generator. Hence |\mathbb Z[\sqrt{-17}]/(3)|=9. We have (3) \subsetneq (3,1+\sqrt{-17}) \subsetneq (1), hence \mathbb Z[\sqrt{-17}]/(3,1+\sqrt{-17}) is a non-trivial quotient of \mathbb Z[\sqrt{-17}]/(3). A non-trivial quotient of a group with 9 elements must have 3 ... 0 Given a+b\sqrt{-17}, you can subtract b(1+\sqrt{-17} to get a rational integer, then subtract an appropriate multiple of 3 to get 0, 1, or 2. So the quotient ring has at most 3 elements, indeed, has number of elements a divisor of 3, so it now suffices to show it's not 1. If it's 1, then 1 is in the ideal, ... 2 Your computations are correct. Since -17\equiv3\bmod{4} our ring of integers is \mathbb{Z}[\sqrt{-17}], so we may factor the ideal (3) in \mathbb{Z}[\sqrt{-17}] by factoring$$x^2 + 17 \equiv x^2 - 1 \equiv (x+1)(x+2) \bmod{3}.$$This yields the ideal (3,1+\sqrt{-17}), and since 3 splits the norm of this ideal is 3. To see this more ... 1 Considering the case when n = 6 only shows that 2^n - 1 is not prime for all composite n (i.e. at least one of 2^n - 1 is composite). However it does not show that 2^n - 1 is not prime for every composite n (i.e. all of 2^n - 1 are composite), which is what is required in the contrapositive form of the question. By invoking the stated ... 3 Is this correct? Yes. Infinite Galois theory provides a bijection between subfields of \overline{\mathbb Q} and closed subgroups of \mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}). Since every open subgroup of a topological group is closed, and the open subgroups all have finite index in \mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q}), both your ... 0 Expand into factorial polynomials and sum the telescoping series.$$\begin{align}\sum_{k=1}^nk(k+4)&=\sum_{k=1}^n\left[k(k+1)+3k\right]\\ &=\sum_{k=1}^n\left[\frac13k(k+1)(k+2)+\frac32k(k+1)-\frac13(k-1)k(k+1)-\frac32k(k-1)\right]\\ &=\frac13n(n+1)(n+2)+\frac32n(n+1)-\frac13(0)(1)(2)-\frac32(1)(0)\\ ...

0

Induction is usually straight forward: 1) n = 1 Does $1*5 = \frac 16*1*(1+1)*(2*1 + 13)$? Yep $5 = \frac 16 2*15 = 5$. So that's the initial step. 2) Suppose true for $n = k$ Does $1*5 + ..... + k(k+4) + (k+1)(k+5) =$ $\frac 16*k(k+1)(2k + 13) + (k+1)(k+5) = \frac 16*(k+1)(k+2)(2(k+1) + 13)$ $=\frac 16(k+1)(k+2)(2k + 15)$? So does $\frac ... 2 A proof without induction: $$\sum_{k=1}^{n}k(k+4)=\sum_{k=1}^{n}k^2+4\sum_{k=1}^{n}k= \frac{n(n+1)(2n+1)}{6}+4\cdot\frac{n(n+1)}{2} =\frac{n(n+1)}{6}(2n+13)$$ 0 With induction, you want to prove a base case and then show that if it works for step$n$then it also works for step$n+1$. If both of those things are true then you're done! Base case,$n=1$: $$1(1+4) = \frac{1}{6}1(1+1)(2(1)+13)$$ $$5 = 5$$ Inductive step: We want to show $$1 \times 5 + ... + (n+1)((n+1)+4) = ... 1$$1 \times 5+2\times6+3\times7 +\cdots +n(n + 4) = =\sum_{i=1}^{n}i^2+\sum_{i=1}^{n}4i=\frac{n(n+1)(2n+1)}{6}+4\frac{n(n+1)}{2}$$7 Base Case: For n = 1, we have:$$ 1 \times 5 = 5 = \frac{1}{6}(1)(1 + 1)(2(1) + 13)$$which works. Inductive Hypothesis: Assume that the claim holds for$n' = n - 1$, where$n \geq 2$. It remains to show that the claim holds for$n' = n\$. Indeed, observe that: \begin{align*} &1 \times 5 +\cdots + n(n + 4) & \\ &= [1 \times 5 + \cdots + (n - ...

Top 50 recent answers are included