# Tag Info

## Hot answers tagged number-theory

18

Given any two rational numbers, $a,b$, note that $a^{\log_a(b)} = b$ is rational but $\log_a(b)$ is generally not rational. For example $2^{\log_2(3)} = 3$ but $\log_2(3)$ is not rational. So a rational number taken to an irrational power can easily be rational. However, if $a\neq 0,1$ is rational (in fact even algebraic) and $b$ is an irrational ...

10

Hint: If you had a solution to $x^n+y^n=z^n$, could you write it as a solution to either $a^p+b^p=c^p$ for some prime $p$ or as a solution to $a^4+b^4=c^4$? (You will only need the latter equation for a very special case. The first will suffice for most.) Double hint: Factor $n$.

10

Here is a partial answer, perhaps someone can fill in a bit more. Throughout the answer, $a_1,a_2,\ldots$ will be positive constants. We use the result $$\int_0^\infty \frac{\sin ax}{x}\,dx =\frac{\pi}{2}{\mathop{\rm sgn}}(a) =\cases{{\textstyle\frac{\pi}{2}}&if a>0\cr 0&if a=0\cr {\textstyle-\frac{\pi}{2}}&if a<0\cr}$$ ...

8

If $p=q$, we have $5^p \equiv 2^p \pmod{p}$ so by Fermat's little theorem, $5 \equiv 2 \pmod{p}$ so $p=3$. This gives the solution $(p, q)=(3, 3)$. Otherwise $p \not =q$, so we may WLOG assume $p>q$. Clearly $q \not =2, 5$, so $(2, q)=(5, q)=1$. Let $d$ be the order of $5 \cdot 2^{-1} \pmod{q}$. Then $(5 \cdot 2^{-1})^p \equiv 1 \pmod{q}$ implies $d ... 5 This is essentially the Gelfond-Schneider Theorem which says: $$\text{If } a,b \text{ are algebraic}, a \neq 0,1 \text{ and } b \in \mathbb{R} \setminus \mathbb{Q} \text{ then } a^b \text{ is transcendental.}$$ Now every transcendental number is also irrational, and every rational number is algebraic.$\sqrt{2}$is also algebraic so in this case, yes ... 5 The probability that two integers, chosen uniformly at random from$1,2,\dots,n$, have greatest common divisor$g$, is (for large$n$)$\displaystyle{6\over\pi^2g^2}$. So the probability that the gcd is less than$B$is$\displaystyle{6\over\pi^2}\sum_{g=1}^{B-1}{1\over g^2}$. A reference is J. Chidambaraswamy and R. Sitarmachandrarao, On the probability ... 4 I don't know why none of the current answers talk about why your methods are wrong and you just happened to get the right answer, so I guess I'll touch on that. First off, it doesn't make any sense to "factor out"$3^5$when the last digit cycles with a length of$4$. Regardless, it's not mathematically wrong, so here's how you would do it using that: ... 4 If$n = p^k$is a prime power, we have $$\sum_{t\mid n} d(t)^3 = \sum_{j=0}^k (j+1)^3 = \left(\sum_{j=0}^k (j+1)\right)^2 = \left(\sum_{t\mid n} d(t)\right)^2$$ by the "similar" identity. For general$n$, use the multiplicativity of$d(\cdot)^m$, that is, for coprime$a,b$we have$d(ab) = d(a)d(b)$, which becomes $$\sum_{t\mid n} d(t)^3 = \prod_{p\mid n} ... 4 Trivial zeros Numerically I found that for n any positive integer (replacing your \,\gamma+\gamma\, constant by \,\log\,\pi\,) :$$\tag{1}\frac{\zeta ''(-2\;n)}{2\,\zeta '(-2\;n)}+\log (n)<\log(\pi)$$with the limit approaching \log\,\pi\, as \,n\to \infty. I obtained too the following asymptotic expansion as \,n\to\infty :$$\frac{\zeta ... 4 Let$\displaystyle n=7^a\cdot\prod p_i^{r_i}$where integer$a\ge0$and$p_i$s are distinct primes and integer$r_i$s$>0$So, the number of divisors of$n$is$\displaystyle(a+1)\prod(r_i+1)=60\ \ \ \ (1)$So, the number of divisors of$7n$will be$\displaystyle(a+1+1)\prod(r_i+1)=80\ \ \ \ (2)$Divide$(2)$by$(1)$to find$a$4 Call$f(x):\Bbb{N}\to\Bbb{N}$the function which, starting from a number, gives out the starting number$+$the bigger digit in that number. Now consider only$2$-digit numbers, and if you come up with a$3$-digit number, then take the last two digits...after some explanation we're ready to start the proof. Note that$f(x) \gt x$, as$f(x)=x+a,a\gt0$, so ... 3 Your function is really just distinguishing between three different categories of integer. The values of$1$,$0$and$-1$that you assign to these categories are entirely arbitrary, so what's of interest here is simply the categories themselves. To make your definition more precise,$f(x)$is:$0$if$\sqrt x$is rational.$1$if$\sqrt x$is irrational ... 3 This is a classic example of a problem which is easily solved via Vieta jumping. We may WLOG assume$x \geq y$. Let us define the "size" of a positive integer solution$(x, y, z)$to be$x+y \in \mathbb{Z}^+$, and say that a solution is a smaller solution if its size is smaller. Given a positive integer solution$(x, y, z)$with$x>y\geq 1$, we shall ... 3 The last digit rotates in a cycle of 4, not 5. You would be better off applying your method starting from 0: 0th power last digit: 1 1st power last digit: 3 2nd power last digit: 9 3rd power last digit: 7 4th power last digit: 1 And continue from there. 3 I'm not sure if your posted answer is correct, but here's one way to think about the problem. How many divisors are there where no prime occurs with maximal multiplicity? This is easy to compute as$\prod_m \alpha_m$since you can choose exponents between$0$and$\alpha_m-1$for each prime divisor, each giving rise to a unique product for each choice. Then ... 3 The sum of the squares of the first$x$consecutive integers, starting from$n+1$, equals $$(n+1)^2+(n+2)^2+\ldots+(n+x)^2=\frac{(n+x)(n+x+1)(2(n+x)+1)}{6}-\frac{n(n+1)(2n+1)}{6}$$ $$=\frac{1}{6}\cdot x\cdot(6n^2+6nx+2x^2+6n+3x+1).$$ For this to be prime we must have$x\mid 6$or $$6n^2+6nx+2x^2+6n+3x+1\mid6.$$ Solving the quadratic equation ... 3 Let our numbers be$a^2,(a+1)^2,\dots,(a+x-1)^2$. The sum of the squares is$a^2 x+2a(1+\cdots+(x-1))+(1^2+\cdots+(x-1)^2)$. Note that$a^2 x$is divisible by$x$, as is$2a(1+\cdots+(x-1))$. So we concentrate on the term$1^2+2^2+\cdots+x^2$. Call this number$N$. By the formula quoted in the post, we have $$6N=(x-1)(x)(2x-1).$$ Suppose that$x\gt 6$. ... 3 This follows from the fact that$\Delta$is an eigenvector for the Hecke operators acting on$M_{12}$. A classical calculation of the effect of Hecke operators at the level of$q$-expansions shows that the Hecke eigenvalues of an eigenform are precisely its Fourier coefficients (more precisely, the$n$-th Hecke eigenvalue is the$n$-th Fourier coefficient). ... 3 The answer happens to be correct, the "method" is not. We have by Quadratic Reciprocity that$(19/61)=(61/19)$. But$61\equiv 4\pmod{19}$, so$(61/19)=(4/19)$. But$4$is a perfect square, so$(4/19)=1$. Remark: Note that$\gcd(7,61)=1$. But$(7/61)=(61/7)=(5/7)=(2/5)=-1$. The fact that$19$and$61$are relatively prime has no reals connection with the ... 2 Let$f(x)=x^n + a_{n-1}x^{n-1}+\dots +a_0\in\mathbb Z[x]$be an integer monic polynomial with$\frac{p}{q}$as a rational root, with$p,q$relatively prime. Then $$q^nf(p/q)=p^n + a_{n-1}p^{n-1}q\dots + a_0q^n=0$$ So$p^n$must be divisible by$q$. Since$p,q$relatively prime, this means that$q=\pm 1$, and therefore$p/q$is an integer. 2 Imagine dividing$7^{100}+3^{10}$by$7^{100}$. The result is a tiny bit bigger than$1$. Divide$8^{100}$by$7^{100}$. We get$\left(\frac{8}{7}\right)^{100}$, which is a very big number, a lot bigger than$1$. Thus$8^{100}$is (an awful lot) bigger than$7^{100}+3^{10}$. 2 One can use the Poisson summation formula: $$\sum_{n\in\mathbb{Z}}f(n)=\sum_{k\in\mathbb{Z}}\hat{f}(k),$$ where$\hat{f}(\nu)$denotes the Fourier transform of$f(t)$, $$\hat{f}(\nu)=\int_{-\infty}^{\infty}f(x)e^{-2\pi i \nu x}dx.$$ Namely, setting$f(t)=e^{-\pi x t^2}$in the above, we obtain $$\theta(x)=\sum_{k\in\mathbb{Z}}\int_{-\infty}^{\infty}e^{-\pi ... 2 Given:$$n = 29, g = 2, ~\mbox{Alice chooses a secret}~ a = 5, \mbox{Bob chooses a secret}~ b = 11$$Alice computes her public value:$$A = 2^5 \pmod{29} = 3$$Bob computes his public value:$$B = 2^{11} \pmod{29} = 18$$They publicly exchange these public values. Alice computes:$$S = B^a \pmod{29} = g^{ba} \pmod {29} = 15$$Bob computes:$$S = ... 2 Since$17$is prime, we can apply Fermat's little theorem: $$a^{17}\equiv a\pmod{17}$$ for any integer$a$. More useful is the statement that $$a^{16}\equiv 1\pmod{17}$$ whenever$17$is not a divisor of$a$. Since$4$is not divisible by$17$, we can write $$102400000002=16\cdot 6400000000+2$$ so $$4^{102400000002}=(4^{16})^{6400000000}\cdot ... 2 One can use p-adic integers for the question which positive integers are sum of three squares. For example, n=7 is not a sum of three squares, but 49=2^2+3^2+6^2 is. The statement is that n is a sum of three squares if and only if -n is a square in \mathbb{Q}_2, the field of 2-adic integers. This is the case if and only if n is not of the ... 2 I changed the notation by mistake, in the following the \alphas are the multiplicities of the primes, and I define w=w(n) (for short) and \Pi_\alpha = \prod_k (\alpha_k-1). We evaluate the contributions that are simple to evaluate in three steps: For each combination of k primes with multiplicity among w in total, the contribution is k(w-k), so ... 2 Finding the last two digits of a essentially \displaystyle a\pmod{100} Now as \displaystyle2012\equiv12, 2012^{2012}\equiv12^{2012}\pmod{100} Again as \displaystyle(12,100)=4 let us find \displaystyle12^{2012-1}\pmod{\frac{100}4} i.e., \displaystyle12^{2011}\pmod{25} Now using Carmichael function or Totient function ... 2 Are the roots of unity well defined in the quaternions, octonions, and other hypercomplex algebras? They can still be defined as elements satisfying x^n=1 for a nonnegative integer n. (I'm not sure what other definition you would use... ) Of course, that doesn't mean that they'll behave as nicely as those roots of unity in the complex plane. I'll ... 2 Let S be the sum of the quadratic residues. As k runs from 1 to p-1, the number k^2 runs (twice) over the quadratic residues modulo p. Thus$$2S\equiv 1^2+2^2+\cdot +(p-1)^2.$$By using the formula for the sum of the first n consecutive squares, we find that$$2S\equiv \frac{(p-1)(p)(2p-1)}{6}\pmod{p},$$and therefore$$12S\equiv ... 2 Starting from 8, the odd residues are given by$(-1)^k3^m$, so clearly, the squares are exactly of the form$3^{2m}$which is a quarter of them. The even residues are squares if they are divisible by 4 and the quotient is a square modulo$2^{n-2}$. So, you get$squares(2^n)=2^{n-3} + squares(2^{n-2})\$ which is easily solved.

Only top voted, non community-wiki answers of a minimum length are eligible