New answers tagged

0

Your approach to Gaussian elimination is fundamentally at odds with the currect state of hardware. You are up against the memory wall, i.e. the fact that floating point operations can be completed at a rate which is far higher than the speed at which data can be retrieved from may memory. By processing your matrix one column at a time, your are constantly ...


0

Your claim is equivalent to the saying that $\{0\} \subset \mathbb{Z}/n\mathbb{Z}$ is a radical ideal in $\mathbb{Z}/n\mathbb{Z}$ only if n is squarefree. This equivalence follows because, for any commutative ring R, an ideal $I \subset R$ is radical if and only if $rad(I) = I$. What exactly is $rad(I)$ (aka the radical of I), you might ask? ...


0

$a|c \implies c = ka$. $b|c \implies b|ka$ but since $gcd(a,b) = 1$, $b|ka \implies b|k \implies k = db \implies c = dba \implies ab|c$.


0

Suppose that $n$ is divisible by $p^2$. Let $a=p$. Since $p^n$ is divisible by $p^2$, the number $p^2$ does not divide $p^n-p$.


0

You ask: how is this method of computing square roots? The answer is: it's pretty good. As written, it's how the Babylonians computed square roots. This is sometimes called "The Babylonian Method." You can do better if you iterate it. Say you are trying to calculate the square root of $S$. If you call $x_0$ the nearest square root below the square root ...


2

Apart from $2$, $3$, $5$ and $7$, every prime number must be relatively prime to $210$. Between $1$ and $210$, there are $\varphi(210) = 48$ numbers prime to $210$. Whether a number is relatively prime to $210$ depends only on its remainder modulo $210$. Therefore for all $k \geq 1$, we have $\pi(210k) \leq 48k + 4$. For any number $n \geq 1$, there is some ...


0

That's just the approximation of binomial expansion. It doesn't work for all but is a very good approximation for many. You used $\sqrt{58} = \sqrt{49+9} = 7\sqrt{1+9/49}$ = $7(1+$$9\over2*49$$)$ $= 7+$$9\over14$ = 7.63 Binomial approximation states - $$(1+x)^n = (1+nx)$$ when $x <<<1$


0

$Proof \ by \ Induction$: $Base \ case$: $n=0, \ n+1=1$. $\;$ $x\mid$$n$ for all $x$$\in$$\mathbb{Z}$, and $1\mid$$1$ trivially holds. Since the only common divisor is 1, $\gcd(0,1)=1$ holds. $Inductive \ Hypothesis$: Assume $\gcd(k,k+1)=1$ for some $k\in$$\mathbb{Z}, \ k>0.$ Let $d=\gcd(k+1,k+2)$, where $d\in$$\mathbb{Z}, \ d>0.$ Hence, ...


0

We can factor: $f(x)=(x^6-1)(x^2+2x+6)$. We are looking for an $n$ such that $\phi(n)=6k$ and such that $-5$ is a quadratic residue $\pmod n$. $21$ makes the job. In fact $\phi(21)=12$ and thus $x^{12} \equiv 1 \pmod {21}$ has 12 solutions, in particular $6$ are good for us! Solving the polynomial of degree $2$ we see that we would love to have a square ...


2

I think n=43 works. The roots are 1, 6, 7, 36, 37, 42, 8, and 33. The first observation is that this polynomial factors over $\mathbb{Z}$ as $(x^6-1)(x^2+2x+6)$. We can actually go further and factor $(x^6-1)$ more, but I don't think it's necessary. The next simplification is to just look for $n$ prime, in particular then the multiplicative group ...


1

Hint We can proceed naively but efficiently. It is plausibly useful to factor $f(x)$ over $\Bbb Q$: $$f(x) = (x^6 - 1)(x^2 + 2 x + 6),$$ and recalling our cyclotomic polynomials, we can easily factor the first factor, giving, respectively, $$f(x) = (x - 1)(x + 1)(x^2 + x + 1)(x^2 - x + 1)(x^2 + 2 x + 6).$$ Obviously, we need $n \geq 7$. On the other hand, ...


0

First important thing to consider is that, when $\cos a$ or $\sin a$ are negative the exponentiation should be done with care, because it is in general multi-valued. For instance, if $\cos a=-1$, then : $$ (-1)^x=e^{i(2k+1)\pi\, x}. $$ In this case, we have a multi-valued expression giving different values for all $k\in\mathbb Z$. However we can always take ...


1

For $Re(s)> 1$ we have the Euler product $$ \frac{1}{\zeta(s)}=\prod_p (1-p^{-s}). $$ Taking the limit $s\to 1$ shows that the infinite product $\prod_p (1-\frac{1}{p})$ is $0$, since $\lim_{s\to 1}\zeta(s)=\infty$. A second possibility is to use that the product $\displaystyle\prod_{n=1}^{\infty} (1- a_n)$ is non-zero if and only if $\sum_{n=1}^{\infty} ...


5

$x = 3^n, y = 2^n$ $$ 3 x^2 + x y - 4 y^2 = (3x + 4y)(x - y)$$


1

This is probably more complicated than you are hoping for, but it at least restates the problem by breaking it into two smaller problems. Suppose you are given some number $A$ and wish to know whether it is equal to the given formula for some $n$ and $s$. If so, then we would have $$\frac{s-2}{2}n^2 - \frac{s-4}{2}n = A$$ which, after some very slight ...


0

We have that $p \equiv$ 2 mod 5 as $q \equiv$ 2 mod 5 and 2 $\times$ 3 = 6, 6 + 1 = 7 $\equiv$ 2 mod 5. Also, we have that $q \equiv$ 1 or 3 mod 4 as $q \equiv$ 3 mod 5. Two cases: If $q \equiv$ 1 mod 4, then $p \equiv$ 3 mod 4 (2(1) + 1 = 3). If $q \equiv$ 3 mod 4, then $p \equiv$ 3 mod 4 (2(3) + 1 = 7 $\equiv$ 3 mod 4) Then we have that ...


3

C150 is the product of the two primes, one with 55 (decimal) digits and one with 96 digits, $P55=1449299471738053389661827008867152641816024786660724327$ and $P96=3113530633988882752054263646036326764738143136281825948356832545797877\ 39684923341337929165875133$. I found these factors using the GMP-ECM algorithm incorporated in Sage, with the initial ...


1

Basically, naming $s=\sigma+it$, the idea is to use the function $$ \xi(s)=\Gamma(s/2)\pi^{-s/2}(s-1)\zeta(s) $$ because it's real-valued on the critical line $t=1/2$, hence you'll find a zero whenever $\xi(1/2+it)$ changes sign. There are various method to do that, a very nice introduction can be found in Edwards' book ``Riemann's Zeta Function", see for ...


1

Here is Euler's Other Proof by Gerald Kimble \begin{align*} \frac{\pi^2}{6}&=\frac{4}{3}\frac{(\arcsin 1)^2}{2}\\ &=\frac{4}{3}\int_0^1\frac{\arcsin x}{\sqrt{1-x^2}}\,dx\\ &=\frac{4}{3}\int_0^1\frac{x+\sum_{n=1}^{\infty}\frac{(2n-1)!!}{(2n)!!}\frac{x^{2n+1}}{2n+1}}{\sqrt{1-x^2}}\,dx\\ &=\frac{4}{3}\int_0^1\frac{x}{\sqrt{1-x^2}}\,dx ...


1

What you're missing is that the equation $d\alpha=0$ is taking place in $P_0/IP_0$, not in $P_0$. Backing up a bit, if $\alpha\in P_1/IP_1$ is a cycle, let's choose a lift $\beta\in P_1$ for $\alpha$. Then you can't necessarily say that $d\beta=0$ as an element of $P_0$, since all you know is that the image of $d\beta$ in the quotient $P_0/IP_0$ is $0$, ...


0

"A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number." - point is that prime numbers are defined as natural numbers so the question is not relevant! Source: Prime Numbers


2

It can be shown by induction on $p$ that $f(a^p) = pf(a)$ for any integers $a,p \geq 1$. We will prove that $f(n) = \log_b n$ for some $b > 1$. After multiplying $f$ by a positive constant, we may assume $f(10) = 1$. Let $n$ be fixed. We will prove that $f(n) = \log n = \log_{10} n$. Otherwise, we have either $f(n) < \log n$ or $f(n) > \log n$. ...


1

I think this result will follow if you assume that given primes $p_1,p_2$ and $\epsilon>0$ there exists integers $n_1,n_2,n_1',n_2'$ such that \begin{equation} 1-\epsilon<\frac{n'_1\log p_1}{n'_2\log p_2}<1<\frac{n_1\log p_1}{n_2\log p_2}<1+\epsilon \end{equation} With this approximation, you can argue that $f(p_1)/f(p_2)$ is arbitrarily close ...


10

Your logic argument for $-1$ being the only negative prime: $-3$, for example, could not be prime because it is equal to $3\cdot(-1)$ $-1$, however, is prime because it is divisible only by itself and by $1$ According to this logic, $+1$ is the only positive prime, since: $3$, for example, could not be prime because it is equal to $(-3)\cdot(-1)$


5

If you think negative numbers are weird, try imaginary numbers. There's not really a good way to think of positive numbers. You could say an imaginary number is positive if its real part is positive, but then you still get results like $(1+2i)(1+2i) = -3+4i$ so you immediately lose the fact that the product of two positive numbers is positive. That means ...


0

Yes the set of integers is closed under multiplication. There are a number of axioms (laws) defining what an integer is. The following three axioms (laws) are important to this argument. 1 is a multiplicative identity. In other words anything multiplied by 1 returns the same value. $ \forall a \in \mathbb{Z}, 1 a = a $ When you add integers together ...


0

Your incorrect interpretation: $[ab=c]\wedge[c\in\mathbb{Z}]\implies[a,b\in\mathbb{Z}]$ The correct interpretation: $[ab=c]\wedge[a,b\in\mathbb{Z}]\implies[c\in\mathbb{Z}]$


0

You have to step back and ask yourself, "what is an integer"? You can't decide if something is an integer or not until you define the integers! Defining the integers requires choosing axioms the integers must satisfied. Picking the "right" axioms so that the definition is consistent, and unambiguous (so that, for instance, you can tell the difference ...


7

You are confusing computer arithmetic with mathematical arithmetic. In a computer, integer arithmetic is exact as long as you don't overflow and $5(n^2-3)$ will always yield an exact integer if $n$ is an integer and the computation is done using integer representations. When you go out of the integers, you use floats, which have a limited number of bits of ...


5

If your computer system does not give an integer when computing $(n-\sqrt3)(n+\sqrt 3)$, then it is because of the floating point arithmetic involved in computing with the irrational number $\sqrt3$. See the section in https://en.m.wikipedia.org/wiki/Floating_point on "accuracy problems." This is a good lesson in realizing that the results of computing ...


1

Hint. Clearly in this case $p$ cannot be $2$ or $5$. So the options are $$p\equiv1,\,3,\,7,\,9\pmod{10}\ .$$ Now while $n$ may have prime factors congruent to $1$ or $9$, it cannot have only such factors, as then multiplying the prime factors together would give... Can you finish this?


0

Hint: Factor $n = ab$ then consider the values $a$ and $b$ may take mod 10.


0

HINT Let $xm-yn=\gcd(m,n)$ so that $x,y$ are positive integers. Note that $a^{xm} \equiv 1 \pmod d$, and that $a^{yn} \equiv 1 \pmod d$. Thus if $a^{\gcd(m,n)} \equiv t \pmod d$, $a^{yn}t \equiv 1 \pmod d$.


1

Hint: In general, the product of two perfect numbers (one odd, the other even) is not perfect, since every nontrivial multiple of a perfect number is abundant. Can you take it from here?


2

Instead of primes, consider the set $S = \{p^{2^n} \space\vert\space n,p \in \mathbb{N}, p \space \text{prime}\}$. These are the primes as well as the squares of primes, fourth powers, eighth powers, etc. Every positive integer can be represented uniquely as a product of distinct elements of $S$, in other words multiplication is a bijection between ...


0

Considering $n=1$, $n=2$ we see that necessarily $15a\in\Bbb Z$ and $48a\in\Bbb Z$. But then already $3a=48a-3\cdot 15a\in\Bbb Z$. On the other hand, if $3a\in \Bbb Z$ then $an(n+2)(n+4)\in\Bbb Z$ for all $n$ because the numbers $n,n+2,n+4$ are pairwise incongruent modulo $3$ and hence one of them is a multiple of $3$. We conclude that $a$ has the desired ...


2

A huge chunk of the literature of p-adic Iwasawa theory is devoted to this question. One of the milestones in the subject is Perrin-Riou's book "P-adic L-functions and p-adic representations", and reading that would be one excellent way to learn the topic. There's also Colmez's Bourbaki seminar "Fonctions L p-adiques", if you're confident reading French. ...


44

If we define prime so that $-1$ is prime, unique factorization into primes fails, since $6=3\cdot 2=3\cdot 2\cdot (-1)^2$. So it is not useful to define $-1$ as a prime. When we get to higher math, we find that when we talk about "primes" in other systems, we are required to treat any pair of numbers that divide each other as "equivalent." That is, if $a$ ...


2

A homeomorphism by definition is a bicontinous BIJECTION. Meaning they must have the same cardinalities. $\mathbb{R}$ has cardinality $2^{\aleph_0}$ while $\mathbb{Q}$ has cardinality $\aleph_0<2^{\aleph_0}$.


0

This answer is about the lim sup version of the definition. It is not the same for a set in this sense to be "dense" (maybe call it "lim sup dense") as it is for a set to be "lim inf dense" (using the lim inf version). We can make $A,B$ disjoint and have each of them "lim sup dense". For each $n=1,2,...$: On step $2n-1$ put enough consecutive naturals in ...


3

Yes. Equivalently, $A$ is dense if its complement $A^c$ satisfies $$ \limsup_{n\to\infty} \frac{\#(A^c \cap \{1,\dots,n\})}n = 0. $$ And this property certainly respects finite addition, since \begin{align*} \#\big((A\cap B)^c \cap \{1,\dots,n\}\big) &= \#\big( (A^c \cap \{1,\dots,n\}) \cup (B^c \cap \{1,\dots,n\}) \big) \\ &\le \#(A^c \cap ...


1

Note that $2 \cdot 2=4, 4 \cdot 3=12, 12 \cdot 7=84, 84 \cdot 43=3612, 3612 \cdot 1807=6526884$. If $k$ is a solution, then it is $\frac {k-2}k + \frac 1k$, where we don't care how $\frac {k-2}k$ is expressed. Then let $m=k(\frac k2+1)$, which is a multiple of $4$ because $k$ is. We have $\frac {m-1}m=\frac {k(\frac k2+1)-1}{k(\frac k2+1)}=\frac ...


2

If prime $p$ divides $x^2-16=(x+4)(x-4),$ $p^3$ must divide $(x+4)(x-4)$ But if $p$ divides both, $p$ must divide $x+4-(x-4)=8$ So, if $p>2,p^3$ must divide exactly one of $x+4,x-4$ For $p=2,$ if the highest power of $2$ that divides $x+4$ is $a$ and $x+4=c2^a$ where $c$ is odd If $a>3, x-4=8(c2^{a-3}-1),$ then $3$ must divide $a$ If $a<3, ...


1

We rewrite the equation as $(x-4)(x+4)=y^3$. We know that $\gcd(x-4,x+4) \mid 8$, so for every prime $p>2$ the factors $p$ are either in $x-4$ or $x+4$. If $y$ is even, at least one of $x-4$ and $x+4$ is divisble by 4, and hence they are both divisible by 4. But then $4 \mid y$, so one of them is divisible by 8 and hence they are both divisible by 8. ...


1

$2^p-1$ is prime implies $p$ is prime. Not the other way around, that is, not every prime $p$ makes $2^p-1$ a prime. For now, there's no way to generate an arbitrary large prime, hence the record of largest prime. The reason we try to find prime of the form $2^p-1$ is partially because of how the computers are designed (working on bits $0$ and $1$).


5

No, a Mersenne prime is a number $m$ such that $$m = 2^n -1$$ is prime. Then $n$ is also prime.


1

As $(45,204)=3$ let us start with $45^{17^{17}-1}\pmod{\dfrac{204}3}$ Using Carmichael function, $\lambda(204)=16$ and $17\equiv1\pmod{16}\implies17^{17}\equiv1$ $\implies45^{17^{17}-1}\equiv1\pmod{68}$ More generally, $a^{17^n-1}\equiv1\pmod{68}$ if $(a,68)=1$ and $n$ is a positive integer Now, $45^{17^{17}-1}\cdot45\equiv1\cdot45\pmod{68\cdot45}$ ...


5

Hint: By the Euler-Fermat theorem we know $45^{\varphi(4)} = 45^{2} \equiv 1 \mod 4$. By the Euler-Fermat theorem we also know $45^{\varphi(17)} = 45^{16} \equiv 1 \mod 17$ It is clear that $45 \equiv 0 \mod 3$ . The Chinese Remainder Theorem gives us now $45^{16} \equiv 69 \mod 204$. Hence $45^{17} \equiv 69 \cdot 45 = 3105 \equiv 45 \mod 204$.


2

Hint: $45\equiv1\pmod4\implies45^n\equiv1$ $45\equiv0\pmod3\implies45^m\equiv0$ $45\equiv11\pmod{17}$ and $17\equiv1\pmod{16}$ and $17^n\equiv1$ $\implies11^{17^{17}}\equiv11\pmod{17}$ Now apply CRT



Top 50 recent answers are included