Tag Info

New answers tagged

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^2$ Then $$ \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 if $a = 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. Let $n$ 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 = 18$ $i = 4$ occurs 16 times. $2 \times 16 = 32$ $i = 6$ occurs 14 times. $1 \times 14 = 14$ $i ...


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$ $q$th 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 $q$th 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