# Tag Info

0

It may be worth mentioning that if $n$ is composite it has a prime factor less than or equal to $\sqrt{n}$. So in this 'trial division' algorithm, you only have to test $n$ for divisibility by primes up to $\sqrt{n}$.

3

Since $\sigma(n)>0$ we have $d<2N$, together with $(2/3)N^2<d$ we get $(2/3)N^2<2N$ which is verified only for $0< N< 3$, which leaves only 2 cases to be checked, namely $1$ and $2$.

2

"In any order" suggests we check the digit sum, which does not depend on order. Turns out ist is $27687\equiv 3\pmod 9$, hence any such number is $\equiv 3\pmod 9$. Perfect powers are either not divisible by $3$ or are divisible by $9$.

2

Hint: Any such number is a multiple of $3$ but not a multiple of $9$.

6

Choose any positive integer $a > n$ such that $\gcd(a,n)=1$ $\because d|n \implies \gcd(a,d)=\gcd(a,n)=1$ By Euler's Theorem, $a^{\phi (n)} \equiv 1 \pmod n$ $\implies n|(a^{\phi (n)}-1)$ $\implies d|(a^{\phi (n)}-1)$ $\implies a^{\phi (n)} \equiv 1 \pmod d$ Again, by Euler's Theorem, since $\gcd(a,d)=1$, $a^{\phi (d)} ... 1 There is unlikely to be a simple closed form solution, given the substantial investigation into how closely this approximates$\pi r^2$. Gauss gave the answer $$1+4\left(\left\lfloor \frac{r^2}{1} \right\rfloor - \left\lfloor \frac{r^2}{3}\right\rfloor + \left\lfloor \frac{r^2}{5}\right\rfloor - \left\lfloor \frac{r^2}{7}\right\rfloor + \cdots \right).$$ 3 Assume you have the Pythagorean relation$u^2 + v^2 = c^2Then \begin{align} (u^2 + v^2) + (u^2 + v^2) & = 2c^2\\ (u^2 + v^2 + 2uv) + (u^2 + v^2 - 2uv) & = 2c^2\\ (u + v)^2 + (u - v)^2 & = 2c^2\\ \end{align} Thus ifa = u + v$and$b = |u - v|a^2 + b^2 = 2c^2$1 Hint: In$\mathbb Z[i]$, let$x:=a+bi$,$y:=c$, then$x\bar x=(1+i)(1-i)y^2$.$\mathbb Z[i]$being UFD implies that$1+i\mid x$or$1-i\mid x$. If$1+i\mid x$, write$z:=\frac x{1+i}=\frac {x(1-i)}2=\frac{a+b}2+\frac{b-a}2i$. Then we have$(\frac{a+b}2)^2+(\frac{b-a}2)^2=z\bar z=y^2=c^2$. 0 Why don't you simply prove it by using alternate definitions of rational and irrational that are, Rational Numbers:$\mathbb Q$If the decimal expansion is non-terminating and contains repeated blocks of digits, as in case of$\frac{1}{3}$and$\frac{1}{6}$, the number is said to be rational. Irrational Numbers:$\mathbb I$If the expansion is ... 6 If$n$is not prime, then at least one of the factors of$n$is at most as large as$\sqrt n$. To see why, let's suppose not. Since$n$is not prime,$n = ab$for some$a,b \neq 1$. If both$a$and$b$are larger than$\sqrt n$, then$a\cdot b > \sqrt n \cdot \sqrt n = n$. This clearly cannot be! So you only need to check for factors up to$\sqrt n$. 0 Note that if$n$is composite, then$n$has a non-trivial factor$i$such that$i \le \sqrt{n}$. Otherwise, any nontrivial factorization$n = ab$would force$a, b > \sqrt{n}$, so that$n = ab > \sqrt{n}\times \sqrt{n} = n$, a contradiction. 5 HINT: I expect that you know that a number is rational if and only if its decimal expansion is eventually periodic. Suppose that the expansion eventually repeats with period$p$. Show that there are two consecutive powers of$2$whose after the initial aperiodic segment whose lengths (when written in the usual way in base ten) are the same multiple of$p$. ... 3 A number is rational if and only if it has an eventually repeating decimal expansion. So you should show that this decimal expansion does not have an eventually repeating expansion. 0 It seems now from the comments that despite the wording of the problem, we are asked to show there are infinitely many irreducibles. This can be done by a straightforward modification of the standard "Euclid" proof, so for fun we show that there are infinitely many primes among the integers of$\mathbb{Q}[\sqrt{d}]$. If$d=-1$,$2$, or$-2$, there is no ... 2 As for an upper bound, we get into work related to Erdos' conjecture on arithmetic progressions (which has not been proven even in the case of arithmetic progression of length 3). I believe the strongest known result is Sander's proof that, if$f(k)$is the size of the largest subset of a$k$-element progression free from arithmetic progression of length ... 1 Roth's Theorem will give you an upper bound: http://wiki.math.toronto.edu/TorontoMathWiki/images/2/2d/Expo_paper.pdf In that paper it is Theorem 1.3 (bottom of first page). It says: Theorem (Roth, 1953) For any$\delta>0$if$k>\exp(\exp(c\delta^{-1}))$(for some absolute constant$c>0$) and$A\subseteq \{1, 2, 3, ..., k\}$and$|A|\geq \delta k$... 0 The bound should depend only on$k$, not at all on$n$. It suffices to find a lower bound on the size of the largest subset of the first$k$positive integers with no arithmetic progression of length$3$. In other words, as user TravisJ explains it, we want the largest subset of$\{1,2,\dots, k\}$. We can achieve a very weak but easy lower bound by simply ... 1 To answer the last part of your question: Let$t_i (1 \le i \le 6)$be any six numbers in$(-\pi/2,\pi/2)$separated by more than$\pi/6$(for instance,$-5\pi/11,-3\pi/11,-\pi/11,\pi/11,3\pi/11,5\pi/11$). Then take$x_i=\tan(t_i)$. 2${\rm mod}\ \color{#c00}{11}\!:\ \overbrace{x^3 \equiv -1}^{\Large x^3\,\ \equiv\,\ 10}\iff x\equiv -1\equiv\color{#0a0}{10}\,\ $by$\ \overbrace{x\equiv x^{3\cdot 7}}^{\Large\color{#a0f}{ 1\ \equiv\ x^{10}}}\equiv (-1)^7\equiv -1\ $by$\,\rm\color{#a0f}{Fermat}{\rm mod}\ \color{#c00}{10}\!:\ x^3\equiv\ \ 0\ \iff x\equiv\ \,0\,\ ...

1

Let the $7$ different numbers be $y_1,y_2,\cdots ,y_7$. Define $7$ angles measured in degrees $x_1, x_2,\cdots, x_7$ such that: $x_i =\tan^{-1} y_i$, then $x_i \neq x_j$, if $i \neq j$, and $x_i \in \left(-90^{\circ}, 90^{\circ}\right)$. Divide this interval into $6$ equal subintervals: $(-90^{\circ}, -60^{\circ}], (-60^{\circ}, -30^{\circ}], \cdots, ... 3 Given$x_1,x_2,\ldots,x_7$, set$x_i = \tan(t_i)$, where$t_i \in \left(-\dfrac{\pi}2, \dfrac{\pi}2\right)$. Divide$\left(-\dfrac{\pi}2, \dfrac{\pi}2\right)$into$6$equal intervals of length$\dfrac{\pi}6$. By PHP, we have two of the$t_i$'s to lie in the same interval, i.e., we have $$-\dfrac{\pi}6 < t_i - t_j < \dfrac{\pi}6$$ Now taking$\tan$on ... 1 Clearly$x=10k$for some$k\in\mathbb Z$. Then$100k^3\equiv 1\pmod {99}\Leftrightarrow k^3\equiv 1\pmod {99}$$$\Rightarrow \pmod {3}: k\equiv 1\text{ or } k^2+k+1\equiv 0$$ In either case,$k\equiv 1\pmod 3$.$(1)$$\Rightarrow\pmod {11} : k\equiv 1\text{ or }k^2+k+1\equiv 0$$ The latter is impossible. To see this, you can simply check by ... 3 Hint: \begin{align}x^3 \equiv 10 \mod 9 \dot \, 11\dot\,10 \iff & x^3 \equiv 10 \mod 9 \equiv 1 \mod 9\\&x^3 \equiv 10 \mod 11 \equiv -1 \mod 11\\&x^3 \equiv 10 \mod 10\equiv 0 \mod 10\end{align} Now observe that $$x^3 \equiv 1 \mod 9 \iff x = 1,4,7 \iff x \equiv 1 \mod 3 \equiv 10 \mod 3\tag{1}$$ $$x^3 \equiv 0 \mod 10 \iff x \equiv 0 ... 2 We have$$x^3 \equiv 10 \pmod{990} \implies x^3 = 990m + 10 = 10(99m+1)$$This means x=10l. Hence, we need$$100l^3 = 99m+1 \implies m \equiv 1\pmod{100}$$Hence,$$x^3 = 10(99(100n+1)+1) = 10(9900n+100) = 1000(99n+1)$$Hence, we need 99n+1 to be a perfect cube. This means$$y^3 \equiv 1\pmod{99} \implies y^3 \equiv 1\pmod9 \text{ and }y^3 \equiv ... 0 Just to allow this question to disappear from the "unanswered" list, here's a rephrase of one of the proves found in the link Elaqqad gave in a comment, with a few minot gaps removed. Letn$be such a number and$p$the smallest prime divisor of$n$(which exists because$n>1$). Write$n=p^km$with$p\nmid m$and$k\ge 1$. We shall show that$m=1$. ... 3 Dirichlet's theorem on arithmetic progressions states that there are infinitely many primes of the form$a\pmod b$, where$\gcd(a,b) = 1$. Pick all odd primes of the form$3k+2$you have in your kitty, say$p_1,p_2,\ldots,p_n$. Now look at the number $$M = 3p_1p_2\ldots p_n + 2$$ Look at the prime factorization of$M$. Clearly, the prime factorization of ... 1 That results from the fact that, norm being multiplicative, a quadratic integer is a unit if and only if its norm is a unit in$\mathbf Z$, and there are not so many units in$\mathbf Z$… Indeed, if$a$and$b$are associates, there is a unit$u$such that$b=ua$. Then $$N(b)=N(ua)=N(u)N(a)=\pm N(a)$$ since the norm of a unit is an invertible element of ... 3 By contradiction using the same argument as Euclid' proof of infinitude of primes First you can assume that$f$has no root in$\Bbb Z$otherwise it's obvious that$f$has a root in every$\Bbb Z_p$Take$g(x)=\frac{f(xf(0))}{f(0)}$(this is a well defined polynomial over$\Bbb Z$), and we have also$g(0)=1$Now assume that$g$has a root modulo only ... 3 HINT: Induction is much easier, but if you really must use Binet’s formula, note that your summations are geometric, with ratios$\alpha^2$and$\beta^2$, respectively; you can use the familiar formula for the sum of a finite geometric series. You also know that$\alpha$and$\beta$satisfy the equation$x^2-x-1=0$, so$\alpha^2-1=\alpha$and ... 0 Alternatively: In$\mathbb Q[\sqrt{-3}]$, the element$\frac{3 + \sqrt{-3}}{2}$is invertible, because $$\left( \frac{3 + \sqrt{-3}}{2} \right)\left( \frac{3-\sqrt{-3}}{6} \right) = 1$$ Whenever you mod out by an invertible element, you end up with a single congruence class. 2 You can use (if$x^2-1\neq 0$): $$\sum_{i=1}^{n}x^{2i-1}=\frac{x^{2n+1}-x}{x^2-1}$$ 1 You can also use Lucas’s theorem. In this context it says that if the binary representations of$m+n$and$n$are$(b_r\ldots b_0)_{\text{two}}$and$(c_r\ldots c_0)_{\text{two}}$, respectively, then $$\binom{n+m}n\equiv\prod_{k=0}^r\binom{b_k}{c_k}\pmod 2\;.$$ The only possibilities for$\binom{b_k}{c_k}$are$\binom01=0$and ... -1 In$\mathbb{Q}[\sqrt{-3}]$all elements are congruent to$3+\dfrac{1}{2}\sqrt{-3}$. Let$\alpha \in\mathbb{Q}[\sqrt{-3}]$. We can write$\alpha$as$a + b\sqrt{-3}$where$a,b\in\mathbb{Q}$. Then$\left(3+\dfrac{1}{2}\sqrt{-3}\right)\left(\dfrac{4a+2b}{13}+\dfrac{12b-2a}{39}\sqrt{-3}\right) = a+b\sqrt{-3}$Thus$3+\dfrac{1}{2}\sqrt{-3}$divides any ... 0 It might be more helpful to do this recursively. Let$T(n) = \prod_{k=1}^n k!$. We will use the notation:$2^{r} \| m$to mean that$2^r$is the largest power of$2$that divides$m$. Then we have$2 \| 2! = T(2)$. We also know that$2 \| 3!$, so$2^2 \| T(3) = 3! T(2)$. Continuing: $$2^3 \| 4!$$ $$2^3 \| 5!$$ $$2^4 \| 6!$$ $$2^4 \| 7!$$ $$2^7 \| 8!$$ ... 0 How many times$2$divides the product$\prod_{i=1}^{19}i!$? Let's call each term inside a factorial$i$. That way,$i = 1$occurs in 19 factorials,$i = 2$occurs in 18 factorials, and$i = 3$occurs in 17 factorials etc.$i = 2$occurs 18 times.$1 \times 18 = 18i = 4$occurs 16 times.$2 \times 16 = 32i = 6$occurs 14 times.$1 \times 14 = 14i ...

2

A simple trick to compute $k$ such that $2^k|n!$ is to compute $\sum_{i=1}^\infty \left\lfloor\frac{n}{2^i}\right\rfloor$, this is because $n$ has $[n/2]$ numbers divided by $2$, if we pick out these numbers and find out that there're $[n/4]$ numbers divided by $4$.. If we continue this procedure, we see that ...

2

$x \equiv 0\pmod{\!17}\!\iff\! x = 17\color{#c00}n.\,$ $\, {\rm mod}\ 9\!:\ {-}1\equiv x\equiv 17n\equiv -n$ $\!\iff\!$ $n\equiv 1$ $\!\iff\!$ $\color{#c00}{n = 1\!+\!9k}$ Therefore $\ x = 17\color{#c00}n = 17(\color{#c00}{1\!+\!9k}) = 17+153k$

-1

Hint first solve $$9x\equiv 1\mod 17$$ which gives $x\equiv2\mod17$. Then solve $$17x\equiv1\mod 9$$ which gives $x\equiv-1\mod9$. Then you will get $$x\equiv 2\times0\times 9+(-1)\times(-1)\times 17=17\mod 153.$$

0

You start with Bézout's identity: $2\cdot 9-1\cdot 17=1$, from which you derive the basic solution: $$x=2\cdot \color{red}{0}\cdot 9-1\cdot(\color{red}{-1})\cdot 17=17.$$

0

The result of Kummer in Theorem $4.3.1$ is about the decomposition of a prime ideal $\mathfrak{p}=(p)$ with a rational prime $p$ in $B=\mathcal{O}_L$, the ring of algebraic integers in $L$. In general, however, we can start with a prime ideal $\mathfrak{p}$ in $\mathcal{O}_K$, and consider its decomposition $$\mathfrak{p}\mathcal{O}_L=P_1^{e_1}\cdots ... 1 One can prove by induction, see e.g. this answer, that every (2^a-1)th row of Pascal's triangle consists entirely of odd entries, i.e. 2^a-1 \choose k is odd for all a,k. Now for fixed m, 2^a-1 the largest number of this form \lt 2m and every n such that m+n \gt 2^a-1 we can use {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k} to ... 1 If p_1,\ldots,p_m are primes congruent to 1 modulo q, then there are 1+(p_i-1)/q qth residues modulo p_i, so a proportion of 1/q + (1-1/q)/p_i, so of about 1/q. Then by the Chinese Remainder Theorem, the proportion of qth residues modulo n = \prod p_i is the product of the proportions for each prime, which is about 1/q^m. By picking ... 1 If \dbinom{m+n}n is odd, this means that the highest power of 2 dividing \dfrac{(m+n)!}{m!n!}. This is given by$$\sum_{k=1}^{\infty} \left(\left\lfloor \dfrac{m+n}{2^k}\right\rfloor - \left\lfloor \dfrac{m}{2^k}\right\rfloor - \left\lfloor \dfrac{n}{2^k}\right\rfloor\right)$$Hence, we need$$\left\lfloor \dfrac{m+n}{2^k}\right\rfloor = \left\lfloor ...

0

A quick experiment strongly suggests it's $n=2^e-m-1$ where $2^e$ is the smallest power of 2 greater than $m$. That this $n$ makes $\binom{m+n}{n}$ odd follows quickly from Lucas' theorem, using the fact that $m+n = 2^e-1 = 2^{e-1}+2^{e-2}+\cdots+1$. That no higher $n$ works follows from the usual formula for the highest power of a prime dividing a ...

3

Kummer's Theorem, a proof of which is given in this answer, in the case $p=2$ says If, when you add $m$ and $n$ in binary, there are no carries, then $\binom{m+n}{n}$ will be odd. Thus, the largest $n\le m$, will be the binary ones'-complement of $m$ (truncated to the size of $m$). For example, if $m=5=101_{\text{two}}$, then $n=10_{\text{two}}=2$. ...

1

The sixth primitive positive one is $$\{a,b,c,d\}=\{1630,2594, 3562, 3878 \}.$$ $$1630+2594+3562+3878=108^2=2^4 3^6;$$ $$1630^2+2594^2+3562^2+3878^2=6092^2;$$ $$1630^3+2594^3+3562^3+3878^3=5004^3.$$ (update) The $7$th such quadruple is $$\{a,b,c,d\}=\{259, 1307, 3485, 9349 \}.$$ $$259+1307+3485+9349=120^2=2^6 3^2 5^2;$$ $$... 1 From the PNT, the average prime gap around n is \sim\log n, therefore the quantity you're interested in can't be bounded above. You can also take a glance on Marek Wolf's work about "jumping champions", which correspond to the most frequent prime gaps in a finite range, and which are conjectured to be the primorials, 2, 6, 30, 210.... It is indeed ... 1 Well, let's look at the structure of the problem: There is a set S of suspects (three in the original problem, a countably infinite number of them in Hilbert's hotel). There's a subset G\subset S of guilty suspects. And there's a mapping f:S\to P(S) where P(S) is the power set (set of subsets) of S, where M\in f(s) means "If s says the ... 1 The existence or not of a non-trivial integer 3x3 magic square of squares is STILL a unsolved problem. The quoted reference to Kevin Brown's web pages only discusses an extremely special configuration of numbers, which does not exist. The page does NOT claim to prove non-existence for all possible magic squares. If you are interested in this topic you ... 0 It sounds to me like you are asking about Infinitary logic. I've pondered this idea myself a fair bit. For instance, we can make sense of the 'limit object' of this sequence$$ a_1 \wedge a_2, (a_1 \wedge a_2) \wedge a_3, (((a_1 \wedge a_2) \wedge a_3) \wedge a_4 where $\wedge$ denotes logical and. In this case the limit object has a value of true if and ...

Top 50 recent answers are included