# Tag Info

## New answers tagged number-theory

6

Note the indices of summation look a lot like years; $\Lambda : \mathbb{N} \to \{0, 1\}$ is the function indicating whether that year had a Congress of Romanian Mathematicians.

9

Perhaps $$\Lambda(i)= \begin{cases} 1\quad\text{if a Congress was held in year }i\\ 0\quad\text{otherwise} \end{cases}$$

0

Ross Millikan is right. Take logs of the numbers and look for a partition of the logs into two nearly sums. This problem is NP-hard. See the Wikipedia page for the partition problem.

0

The equation can be re-written as $(dx)^2+(dy)^2+(dz)^2=(dx)(dy)dz)$ i.e $(dx,dy,dz)$ are solutions to $a^2+b^2+c^2=abc$ In the above equation if any one of $a,b,c \equiv 0 \$mod $3$ then the RHS is $\equiv 0$ mod $3$. This means that all of $a,b,c$ have to be divisible by 3. If $a^2,b^2,c^2$ are $\equiv 1$ mod $3$ then LHS will be $\equiv 0$ mod $3$ ...

1

Yes, the pair of functions $\zeta(s)^2 \pm \zeta(1-s)^2$ has zeroes at all the nontrivial zeroes of $\zeta(s)$. In general, $$\pi^{-s/2} \Gamma \left( \frac{s}{2} \right) \zeta(s) := \Lambda(s) = \Lambda(1-s)$$ and neither powers of $\pi$ nor the Gamma function have zeroes in the critical strip. So if $\zeta(\rho) = 0$, then $\zeta(1 - \rho) = 0$. This ...

-1

Let $\sqrt3 = a + b\theta + c\theta^2 + d\theta^3$ with $a,b,c,d \in \Bbb Q$. Since the trace function($T$) is linear and $T(x) = x$ for $x \in \Bbb Q$: $$T(\sqrt3) = a + bTr(\theta) + cTr(\theta^2) + d(\theta^3)$$ Everything except $a$ is $0$ here. Therefore, $a = 0$ as well. Divide both sides by $\sqrt 2$ and take the trace again, repeat till ...

2

By the Unique Factorization Theorem, it is enough to prove the result for integers $a, b, c$ which are each powers of a prime $p$. Let $a=p^\alpha$, $b=p^\beta$, and $c=p^\gamma$. Without loss of generality we may assume that $0\le \alpha\le \beta\le \gamma$. Then $\text{lcm}(ab,bc,ca)=p^{\beta+\gamma}$ and $\gcd(a,b,c)=p^\alpha$, so the product is ...

-1

If $$gcd(a,b,c) = k$$ Then $$LCM(ab,bc,ca) = abc/(Factors\text{ } shared \text{ } by \text{ } abc)$$ Since if you multiplied $ab$ by $c$ and $bc$ by $a$ and $ca$ by $b$ then it is easy to see that $abc$ is a common multiple of $(ab,bc,ca)$. It may not be the lowest common multiple since the numbers we multiplied by might have been redundant by having ...

1

This is conditional on Dickson's conjecture, but may be of interest. You may choose any admissible prime k-tuple $(b_1=0,b_2,b_3,\ldots,b_k)$. By definition the $b_i$ avoid some residue modulo every prime, and hence so do $\{(2+b_i)n+1\}$. Then it is a consequence of Dickson's conjecture that $q_i=(2+b_i)n+1$ are simultaneously prime for $1\le i \le k$ for ...

1

Another way without Euclid's lemma: the table of squares modulo $6$ is : $$\begin{matrix} n\equiv {}&0 &\pm1 & \pm2&3\\[1ex] \hline n^2\equiv {}&0&1&-2&3 \end{matrix}$$ We see the only case with $\,n^2\equiv 0 \bmod 6$ is when $n\equiv 0$.

1

without Euclid: if $6|n^2$, $n^2=2^{2i}3^{2j}p_3^{2k}p_4^{2l}...p_q^{2m},\{i,j,k,l,m...\}\in N$ now take the square root of that. for other way obvious that $6|n\Rightarrow 6|n^2$

6

The main result is Euclid's lemma: If $p$ is prime and $p$ divides $ab$, then $p$ divides $a$ or $p$ divides $b$. Now $6$ divides $m$ iff $2$ and $3$ divide $m$. Apply these two facts to $6$ divides $n^2$ to conclude that $2$ and $3$ divide $n^2$ and so that $2$ and $3$ divide $n$.

3

What follows does not match the question exactly but may be interesting to know. Observe that the Dirichlet series of the indicator function of squarefree numbers is $$L(s) = \prod_p \left(1+\frac{1}{p^s}\right).$$ If these are supposed to be co-prime with $m$ we get $$L(s) = \prod_{p|m} \frac{1}{1+\frac{1}{p^s}} \prod_p ... 0 You seem to be asking: "How do I find all primitive triples with a leg equal to a given number, say 45?". A simple method is to use the "Fibonacci Box" shown below where q',q are positive coprime integers with q' odd, and where q'+q=p and q+p=p'.$$ \left[ {\begin{array}{*{20}{c}} q & q' \\ p & p' \end{array}} \right]$$Then: ... 3 Perhaps rather strangely, there is not a simple standard definition of "number". In the third century BC, Euclid took "number" to mean one of 2,3,4,5,\ldots, a sequence starting with 2 and closed under the operation of adding a unit, i.e. if n is a number, then so is n+1, so the sequence continues infinitely. Euclid did not consider the "unit" to ... 1 Formally, we would describe numbers as "mathematical objects used to count, measure or label". However, this definition seems to apply more to real numbers, that is numbers we use in everyday life (2, 5, \pi ...). There exist certain quantities, which we call numbers, that cannot be assigned to a measure or label in real life. Therefore, depending on how ... 1 You can use another induction, which is useful to understand the Extended Euclidean algorithm: it consists in proving that all successive remainders in the algorithm satisfy a Bézout's identity whatever the number of steps, by a finite induction or order 2. Initialisation is easy, as the first two remainders are r_0=a and r_1=b, you have:$$a=1\cdot ...

2

Suppose $g(x) = \sum_{n \leq x} f(n)$ denotes the partial sums of the arithmetic function $f(x)$. Then the heuristic in the post you mention follows from the intuitive idea behind the derivative. That is, consider $g(M) - g(N)$, the sum of the last $(M-N)$ elements in the partial sum of $f(n)$. If we're interested in the average size of $f(n)$, then we are ...

0

We have two congruences $$(1)\hspace{1cm}{2p-1\choose p-1}\equiv 1\!\!\!\mod p^2,\hspace{10mm}\text{and}\hspace{10mm} {ap\choose bp}\equiv {a\choose b}\!\!\! \mod p^2,\,\, a,b,\in\mathbb{N}.\hspace{1.1cm}(2)$$ We would like to obtain $(2)$ from $(1)$. Both congruences actually hold modulo $p^3$. For $k$ an integer, define $c_k=(kp-1)(kp-2)\ldots(kp-p+1) ... 0 An approach from the other side. Any Pythagorean triple can be generated from two non zero integers$m,n$by: $$a=m^2-n^2 \qquad b=2mn \qquad c=m^2+n^2$$ For an arithmetic progression we need: $$b-a=2mn-m^2+n^2=m^2+n^2-2mn=c-b$$ and solving we find$2n=m$so that all such triple have the form $$a=3n \qquad b=4n \qquad c=5n$$ For a geometric ... 0 For the first part If$x,y,z$are in arithmetic progression, then $$2y=x+z$$ or the same with$x,y$interchanged. Then $$x^2+y^2=z^2 \Rightarrow \\y^2=z^2-x^2=(z-x)(z+x)=(z-x)2y$$ This gives $$x+z=2y \\ z-x=\frac{y}{2}$$ This gives$x=\frac{3y}{4}$and$z=\frac{5y}{4}$. Deduce that$4|y$and the writing$y=4k$you get the arithmetic progression ... 2 If the sides are in arithmetic progression, WLOG we can choose the sides to be$a-d,a,a+d$where$a,a-d>0\iff a>d$So,$(a-d)^2+a^2=(a+d)^2\iff a^2=(a+d)^2-(a-d)^2=4ad\iff a(a-4d)=0\implies a=4d$as$a\ne0$For Geometric Progression, let the sides be$a,ak,ak^2$where$a>0,k\ge1$So,$a^2+(ak)^2=(ak^2)^2\implies k^4-k^2-1=0$as$a\ne0$... 1 It is Piere de Fermat (1601-1665) who proved that$n=1$is NOT a congruent number, and also that$n=2$is NOT congruent. A discussion of his proof may be found in J.D. Sally and P.J. Sally Jr. Roots to Research. American Mathematical Society, Ch 2, p97, 2007. A congruent number$n$is defined as the integer area of a rational right triangle. When$n$is ... 0 You can use fast exponentiation: modulo$100$$$33^2\equiv -11,\quad 33^4\equiv 21,\quad 33^8\equiv 441\equiv 41,\quad 33^{16}\equiv1681\equiv -19$$ whence$\,33^{20}\equiv -19\cdot 21 =-(20-1)(20+1)=\equiv 1$. 3 It is not true.$2^{16} - 1^{16} \equiv 99 \pmod {133}$An easy way to show it without a calculator is that$7$divides$133$, so$7^{16}$is a multiple of$7$and$1^{16}$is not. 3$2^{16}-1 = 3\cdot 5\cdot 17\cdot 257 $so there is no way that$133=7\cdot 19$divides$a^{16}-b^{16}$if$(a,b)=(2,1)$. 2 Hint:$33^2\equiv-11\bmod100$. 1 Hint:$9^2~=~81~=~5\cdot16+1$. 4 Alternative to other answers: Note that$9^2=81\equiv 1\pmod{16}$, so$777^{777}\equiv 9^{777}=9\cdot(9^2)^{388}\equiv 9\pmod{16}$. 1 Since$9$is coprime to$16$, you know that $$9^{\varphi(16)}\equiv 1\pmod{16}$$ where$\varphi$is Euler's totient function. Your method is good, but$\phi(16)\ne 16-1$, so you got the answer wrong. 1 Fermat's theorem will only work with primes.($16$is not a prime) But, it can be solved by the general formula, using Euler's theorem. Since$gcd(9,16)=1, 9^{\phi(16)} \equiv 1 (mod 16)$. Since$16=2^4, \phi(16)=8$. Therefore,$9^8 \equiv 1 (mod 16)$, and we have$777^{777} \equiv 9^{777} \equiv 9^9 \equiv 9*9^8 \equiv 9 (mod 16)$. 1 Hint:$1000$is divisible by$8$. So if$\overline{23487k2}$is divisible by 8,$\overline{7k2}$is divisible by 8. So we have$702+10k$is divisible by$8\implies 6+2k$is divisible by$8$1 For the second, since we have $$10^3\equiv (-3)^3\equiv -27\equiv -1\pmod{13},$$ we have $$(231)\cdot (10^3)^2+(40+*)\cdot 10^3+791\equiv 0\pmod{13}$$ $$\Rightarrow 10\cdot 1+(1+*)\cdot (-1)+11\equiv 0\pmod{13}$$ $$\Rightarrow *\equiv 10-1+11\equiv 7\pmod{13}$$ Hence, we have$*=\color{red}{7}$. (This is sufficient.) For the third, it is divisible by$9$, ... 0 Hint: Write$x_j=q_jm+r_j,j\in{\Bbb{N}}$. We have $$x_j\equiv r_j\pmod{m}$$ For$j=1 \text{ to } n$, we have$n$similar relationship. What can you conclude? 0 Note that this problem is equivalent to the problem of partitioning$n$into$4$parts. In number theory, a partition is one in which the order of the parts is unimportant. Under these conditions, we are under the illusion that the order is important, however we can only order any given combination of$4$parts in$1$way. Thus, the order is unimportant. ... 0 You can write a generating function for this problem. Let me generalize your question. For$n\in\mathbb{N}_0$and$k\in\mathbb{N}$, let$a_k^n$be the number of ways to write$n$as a sum$x_1+x_2+\ldots+x_k$of integers$x_1,x_2,\ldots,x_k$such that$0\leq x_1\leq x_2 \leq \ldots \leq x_k$. Observe that this is the same problem as writing$n$in the ... 2 We can begin with Wilson's Theorem$(p-1)!=-1\mod p$. This allows$\dfrac{(kp-1)!}{(k-1)p!}=-1\mod p$, for example with$p=5$and$k=2$,$9.8.7.6=3024\equiv-1\mod5$, because we are looking at$(kp-1)(kp-2)\dots ((k-1)p+1)$in which the terms without a$p$coefficient relate to Wilson's Theorem. So we have$\binom{2p-1}{p-1}\equiv1\mod p^2$, using ... 2 A different approach: One could rewrite the problem as:$ 6*7^{32} + 7*9^{45} = 6* (8-1)^{32} + 7* (8+1)^{45} $and then apply the binomial theorem.$ (8-1)^{32} = \binom{32}{0}*8^{32} *(-1)^0 + \binom{32}{0}*8^{31} *(-1)^1 ... + \binom{32}{0}*8^0 *(-1)^{32}  (8+1)^{45} = \binom{45}{0}*8^{45} *(+1)^0 + \binom{45}{0}*8^{44} *(+1)^1 ... + ...

2

You have to show that $70! \equiv 63! \mod 71$, so it suffices to show that $70 \cdot 69\cdot 68\cdot 67\cdot 66 \cdot 65 \cdot 64 \equiv 1 \mod 71$. This holds because of $70 \cdot 69\cdot 68\cdot 67\cdot 66 \cdot 65 \cdot 64 \equiv (-1)\cdot (-2)\cdot (-3)\cdot (-4)\cdot (-5)\cdot (-6)\cdot (-7) \equiv -720 \cdot 7 \equiv -10 \cdot 7 \equiv -70 \equiv 1 ... 8 Hint:$64\times 65 \dots \times 70 \equiv -7\times -6 \dots \times -1$To break it down further try 2 Reduction modulo an integer is a homomorphism of rings ie $$a+b \pmod n=a \pmod n+b\pmod n$$ and $$a\times b\pmod n=a\pmod n\times b \pmod n$$ These facts are easy to check directly e.g.$(a+pn)(b+qn)=ab+(aq+bp+pqn)n$and$(a+pn)+(b+qn)=a+b+(p+q)n$. This means that it doesn't matter whether you do your reductions first and the arithmetic after, or do the ... 1$\phi(4) = 2$and since$(4,7), (4,9)$are relatively prime we have$[7^2]_4 = [1]_4$,$[9^2]_4 = [1]_4$and so$[6 \cdot 7^{32}+7 \cdot 9^{45}]_4 = [6]_4+[7 \cdot 9]_4=[69]_4 = [1]_4$. 1$[6\equiv\color\red2\pmod4]\wedge[7^{32}\equiv\color\green1\pmod4]\implies[6\cdot7^{32}\equiv\color\red2\cdot\color\green1\equiv\color\purple2\pmod4][7\equiv\color\red3\pmod4]\wedge[9^{45}\equiv\color\green1\pmod4]\implies[7\cdot9^{45}\equiv\color\red3\cdot\color\green1\equiv\color\orange3\pmod4]$... 4 The relation "go modulo 4" is very nice. It respects addition and multiplication. So $$6 \cdot 7^{32} + 7 \cdot 9^{45}$$ is the same as $$6 \cdot 1 + 7 \cdot 1$$ by what you have already computed! 1 You're on the right track. Note that$9 = 1 \mod 4$, so$9^{45} = 1 \mod 4$. Then just apply normal rules. You have$6\times 1+7\times 1=13=1$2 $$6 \cdot 7^{32} + 7 \cdot 9^{45} \equiv 6 \cdot 1 + 7 \cdot 1 \equiv 6+7 \equiv 13 \equiv 1 \mod 4$$ 4 If you want$10$pairs, or infinitely many, note that if$k\ge 1$then$\varphi(3\cdot 2^k)=\varphi(2^{k+1})$. One can also generate infinitely many triples, playing a similar game with$5\cdot 2^k$,$3\cdot 2^{k+1}$, and$2^{k+2}$. By playing with small numbers, we can find many other examples. For instance,$\varphi(7)=\varphi(9)$and we can get an ... 0 Lemma$\ $If$\ \color{#0a0}{(a,b,c,d)= 1}\ $then$\ \color{#c00}{ab = cd}\,\Rightarrow\, d = (a,d)(b,d)$Proof$\,\ (a,d)(b,d) = (\color{#c00}{ab},ad,bd,d^2) = (\color{#c00}{cd},(a,b,d)d) = \color{#0a0}{(c,a,b,d)}d = d\ \ \ $QED Thus if$\ (a,d) = n = (b,d)\ $then$\ d = (a,d)(b,d) = n^2.\ $This applies to OP since clearing denom's yields$\,ab = ...

5

In my opinion Hardy &Wright's book on Number Theory is not the best possible book for someone "who has no prior training in Number Theory", I would suggest the following books. Elementary Number theory by David M. Burton. Number Theory A Historical Approach by John H. Watkins Higher Arithmetic by H. Davenport All the books are ...

2

Dover publishes many number theory titles. At \$10-\$15 each they're a bargain - no need even to look for the Amazon discount. You can get several and jump back and forth among them to get different perspectives on each topic. You can write yourself notes in the margins. Take them to the library to read. This is a standard old undergraduate text: ...

Top 50 recent answers are included