Tag Info

Hot answers tagged

10

Both formulas amount ot $\frac{n(n+1)}{2}$ (where the numerator is even because one of $n, n+1$ is even). This is a well-known result and anecdotally attributed to Gauß who - as a child - is said to have solved the summation $1+2+\ldots +100$ within seconds, much to the surprise of his teacher who hd posed the problem in order to keep his class busy for a ...


7

In general a number with prime factorization $p_1^{a_1}p_2^{a_2}\cdots p_{k}^{a_k}$ has $\prod_{i=1}^{k}(a_i+1)$ divisors: the prime $p_i$ can occur from $0$ to $a_i$ times in each divisor. So to find all numbers with exactly $32$ divisors, first find all factorizations of $32$. There are a number of these; each one corresponds to a family of numbers with ...


7

Found why it's $-1$. Rewrite the equation as :$$n\bigg(\frac{1+\frac1n\sqrt{n^2 + 4n}}{2}\bigg)$$ The square root can be written as $\sqrt{n^2(1+4/n)} = |n|\sqrt{1+4/n} = -n\sqrt{1+4/n}$ because $n<0$. Then you obtain : \begin{eqnarray*} \phi(n) &=& \frac{n}{2}\big(1-\sqrt{1+4/n}\big)\\ &=& \frac n2(1-(1+\frac2n) + O(n^{-2}))\\ ...


7

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 ...


6

Multiplying the first $32$ primes together would not work. Even multiplying the first three primes together gives you a number: $30$, with $8$ divisors: $\{1, 2, 3, 5, 6, 10, 15, 30\}$. The number of divisors of a number is a multiplicative function, and since each prime has $2$ divisors, the product of $n$ distinct primes has $2^n$ divisors. That fact ...


5

HINT: As $(a-b)|(a^n-b^n)$ for integer $n\ge0$ i.e., $\displaystyle a^n-b^n\equiv0\pmod{a-b}$ (See Why $a^n - b^n$ is divisible by $a-b$?) $\displaystyle17^n-12^n\equiv0\pmod{17-12}$ and $\displaystyle24^n-19^n\equiv0\pmod{24-19}$ and $24^n-17^n\equiv0\pmod{24-17}$ and $\displaystyle19^n-12^n\equiv0\pmod{19-12}$ Finally, $(5,7)=1\implies$lcm$(5,7)=?$


4

There cannot be. First, if $x$ is rational, say $a/b$ where $a,b$ are relatively prime, let $q=p$ be a prime number. Then $q^x$ is irrational, because the $b$-th root of an integer is rational iff it is itself an integer. However, $x$ cannot be irrational, since it follows from the six exponentials theorem that if $p,q,r$ are three distinct primes, and ...


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 ...


4

Suppose that $x + y$ is an integer, but that $y$ is not an integer, while $x$ is. Then $y = \left( {x + y} \right) + \left( { - x} \right)$, and since the sum of integers is an integer (you've shown that a sum of integers is an integer, and $x$ is an integer implies $ - x$ is an integer), and ${x + y}$ and $x$ are both integers, we conclude that $y$ is also ...


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

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} ...


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

Here is a method you can try. Let $s_1=a+b+c$, $s_2=a^2+b^2+c^2$, $p_2=ab+bc+ac$, $p_3=abc$ $a, b, c$ are the roots of the cubic $$0=(x-a)(x-b)(x-c)=x^3-s_1x^2+p_2x-p_3$$ We don't know $p_2$ but can calculate it using $s_1^2=s_2+2p_2$, and then solve the cubic to find $a,b,c$.


3

Even numbers are just numbers that can be cut in half. Or, another way, if you have an even number of objects, you can sort them in pairs of two, or you can split them into two equally sized groups. The odd numbers are those where you can't do that. This is generalizable to other numbers, so $n$ is divisible by $k$ if you can sort $n$ objects into groups of ...


3

Think of indivisible bricks, and houses: $\,\,\,\,$ You can cut the first house into two equal parts. But you're not strong enough to cut the second house into two equal part, since you'd be left with one brick. For divisibility, build houses with bases containing $m$ bricks. Then the total number of full floors is the quotient of the total number of ...


3

The wikipedia entry is reasonably coherent, and is pretty up-to-date. The twin prime conjecture itself remains open, but there has been recent remarkable progress on slightly weaker results. Namely, Y. Zhang proved that there is an infinite sequence of primes $p_n$ such that $p_{n+1} - p_n$ is uniformly bounded. (This result is referred to as bounded prime ...


3

Because $\phi(19)=18$, we have $2^a\equiv 2^b\pmod{19}$ if and only if $a\equiv b\pmod{18}$. This is equivalent to Fermat's Little Theorem. Hence you need to find a small number $m$ such that $2^n\equiv m\pmod{18}$. We compute and see the pattern mod 18: $2^1\equiv 2, 2^2\equiv 4, 2^3\equiv 8, 2^4\equiv 16, 2^5\equiv 32\equiv 14, 2^6\equiv 28\equiv 10, ...


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

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 ...


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

This is not the case if at least one of $a,b$ and at least one of $c,d$ is not a perfect square: Assume that $b,d$ are not perfect squares. Note that for an integer $a\geq 1$ and a prime $p \not \mid a$: $$a^\frac{p-1}{2} \equiv \left(\frac{a}{p}\right) \bmod p.$$ Therefore it is enough to give a prime $p$ such that the system of equations $$ ...


2

Most of functions used in analytic number theory are multiplicative, that is, they satisfy the identity $$f(mn)=f(m)f(n)$$ when $m$ and $n$ are coprime. But $\nu(8)\nu(27)=(-1)(-1)=1$ and $\nu(216)=-1$. I'm somewhat famirialized with analytic number theory and I don't know any use for this $\nu$ function, or special properties. Nevertheless, you can never ...


2

Both results are the same, and are an instance of the formula for the sum of an arithmetic progression, in which each term is obtained from the previous one by adding a constant increment. In general the sum of such a progression is the product of its number of terms times the average of its first and last terms. Maybe you can see right away why this is so ...


2

We assume that variables range over the integers. We also assume that our language has equality, and binary function symbols $S$ and $P$ for addition and multiplication. We will be careless about parentheses. We need to introduce certain abbreviations: We write $x+y$ instead of $S(x,y)$ and $xy$ instead of $P(x,y)$. $x^2$ abbreviates $xx$ ...


2

I'm assuming $a,n$ are positive integers. First of all, $a^{n+1}-(a+1)^n \equiv -1 \equiv 2001 \;\; \text{mod} \; a ,$ so $a$ divides $2002=2 \times 7 \times 11 \times 13. $ Because $3|2001$ then $a^{n+1} \equiv (a+1)^n \;\; \text{mod} \; 3.$ You can easily eliminate $a \equiv 0,-1 \;\; \text{mod} \; 3,$ therefore, $a \equiv 1 \;\; \text{mod} \; 3 ...


2

Look at 7. Two possibilities: $7|(p-1)$ with $p|n$: hence $p = 14k+1 \in \{ 29, 43\}$ (the others are too big). If $p=29$, $\phi(n) = 28\times 3 = (29-1)(3)$. 3 has to be some $(p-1)p^{a-1}$ but $p=4$ is not prime. If $p=43$, you have the solution $\phi(n) = 42\times 2\implies n = 43\times 3$ or $n = 43\times 2^2$. Otherwise: $7|n$. $\phi(n) = 6\times ...


2

Note that $$9 \equiv -2 \pmod{11} \implies 9^5 \equiv (-2)^5 \pmod{11} \equiv 1\pmod{11}$$ Hence, \begin{align} 9^{2012} & \equiv 9^{2010} \cdot 9^2 \pmod{11}\\ & \equiv \left(9^{2010}\pmod{11} \right)\cdot\left( 9^2 \pmod{11} \right)\\ & \equiv \left(\left(9^5\right)^{402}\pmod{11} \right)\cdot\left( 9^2 \pmod{11} \right)\\ & \equiv ...


2

The two answers provided are spot on. I will add some more about Fermat's Little Theorem, though. It states that for $p$ a prime, that $a^{p} \equiv a \pmod{p}$. This gives us $a^{p-1} \equiv 1 \pmod{p}$. So we can factor out the coefficients and use rules of exponents to simplify, as LACarguy did above. User141421 used a corollary to a theorem from ...


2

If $N$ has prime factors $pqr$ then $N = p^2qr$ since there is only one way to partition $12$ into $3$ parts with each part $> 1$ and the product of these parts begin equal to $12$. Since the sum of the prime factors is even, one of them must be $2$ and to minimize $N, 2 = p$. Then $q = 7, r = 11$ to minimize $N$.



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