Tag Info

New answers tagged

10

You read the clock wrong (though it's not really your fault). ...


0

If a programmatic solution (Python 2.7) is acceptable, then: for n in range(0,100): if (n*n)%100 == n: print "%04d"%(n*n) Gives: 0000 0001 0625 5776


2

We need $D^2\equiv D\pmod{10}$ hence $D(D-1)$ must be a multiple of $10$. This implies that $D\in\{0,1,5,6\}$. Next, the tens digit of $(CD)^2=(10\cdot C+D)^2=100\cdot C^2+20\cdot C\cdot D+D^2$ is determined by the ones digit of $2\cdot C\cdot D$ and the tens digit of $D^2$. For $D=0$ we need $2\cdot 0\cdot C\equiv C\pmod {10}$, so $C=0$. For $D=1$ we ...


0

If you allow leading zeros, there are three more. $D$ must be $0,1,5,6$. You can then just try them all-there are only $40$ possibilities. As $0,1$ don't carry, in both cases we must have $C=0$. For $5$ it has to be $2$, giving $00,01,25,76$


1

If you already proved that $$\sum_{n\leq x}\Lambda\left(n\right)=O\left(x\right) $$ you can conclude directly because $$\int_{1}^{x}\frac{1}{t}\left(\sum_{n\leq t}\Lambda\left(n\right)\right)dt=O\left(\int_{1}^{x}\frac{1}{t}tdt\right)=O\left(x\right) $$ and this complete your proof. If you use your argument $$\sum_{n\leq ...


0

$$\lim_{x\to\infty}\frac{\log(x)^n}{x^m}= 0$$ for any $n>0$ and $m>0$ so $O(\log(x)^n)$ is a tighter bound and can be replaced by $O(x^m)$ if it is more convenient. However the inverse will not be true.


1

An approach : A number $n$ can be representated by $xa+yb$ with integers $x,y$ (not necessarily positive!) if and only if $n$ is a multiple of $g:=gcd(a,b)$ We can assume $gcd(a,b)=1$ because if $gcd(a,b)=g$ we can set $a'=\frac{a}{g}$, $b'=\frac{b}{g}$ and $n$ can be represented by $xa'+yb'$ if and only if $ng$ can be represented by $xa+xb$. In other ...


1

From a purely algorithmic perspective, a priority-first search should work fine for the parameters given; it's logarithmic in $a$ and $b$, and roughly linear in $k$ (depending on your implementation). At stage $k$, this algorithm produces the $k$-th smallest expressible number; it also maintains a list $C$ of "candidates" as a priority queue. Initially ...


2

Adding to the existing answers, note that if your number isn't quite in the right form, you can get it that way easily; so if you want to know about $N=1.02371717171\cdots$, you can write $$1000N=1023+ 0.717171\cdots$$ Apply the method mentioned in the other answers to write the repeating part as a fraction $$1000N=1023 +\frac ab$$ then isolate $N$ again: ...


2

To illustrate the method lets take 0.13131313131313131313... as an example Let $x = 0.13131313131313131313...$ We now multiply by a suitable power of 10 such that the fractional part is the same. In this case 100 $100x = 13.13131313131313131313... = 13 + x$ Thus $99x = 13 \Rightarrow x = \dfrac{13}{99}$ For your second example you need to multiply by a ...


1

Multiplying your number by a suitable power of $10$ we can make some parts the nummber jump to the left of the decimal point leaving identical fractional part. That is $10^mx$ and $x$ have the same fractional part. SO their difference is an integer $a$: That is $a= (10^k-1)x$, this shows $x$ is a rational number.


0

Proof of closure of multiplication of positive rational numbers: Let $q_1,q_2\in\mathbb{Q}^+$. Then $q_1 = \frac{a}{b}$ and $q_2=\frac{c}{d}$ where $(a,b,c,d)\in(\mathbb{N}\setminus\{0\})^4$. You have then that $q_1\cdot q_2 = \frac{a}{b}\cdot \frac{c}{d}$ which by definition of multiplication of rational numbers becomes $\frac{a\cdot b}{c\cdot d}$. Note ...


2

The norm for the ring of integers $\mathbb{Z}\left[\frac{1 + \sqrt{-11}}{2}\right]$ is a binary quadratic form over $\mathbb{Z}$. Sorry for bulky notation: $$\big|\big|x + \tfrac{1 + \sqrt{-11}}{2}y \big|\big|^2 = x^2 + xy + 3y^2$$ The "unit circle" for this norm is actually a tilted ellipse. Using a change of variables $x' = x + \tfrac{1}{2}y = \cos ...


0

for (1) (it should help you with ideas for (2) as well) $\sigma(n)$ is the sum of divisors of $n$. In your case $n=2k=2^{p-1}q$ where $q=2^p-1$ itself being a prime. So all possible divisors of $n$ will be of the form $2^aq^b$, where $a \in \{0,1,2, \ldots , p-1\}$ and $b \in \{0,1\}$. So \begin{align*} \sigma(2k) & ...


3

By little Fermat theorem we have $a^p=a(\mathrm{mod} p)$, and hence $p^2$ divides $(a^p-a)^{p-r}$ if $r\neq p-1$ or $p$. Therefore, the summands in the left hand side are not divided by $p^2$ only if $p-1$ or $p$. Now $\mathrm{LSH}=p(a^p-a)a^{p-1}+a^p=a^p(\mathrm{mod} p^2)$.


4

Let's consider the terms in the summation for $0<r<p$, which are all divisible by $$ \binom{p}{r}(a^p-a). $$ Since $\binom{p}{r}$ is divisible by $p$ and, by Fermat's little theorem, $a^p-a$ is also divisible by $p$, the term is divisible by $p^2$; therefore $$ p^2\Bigm| \binom{p}{r}(a^p-p)^{p-r}. $$ Thus $$ a^{p^2}\equiv (a^p-a)^p+a^p\pmod{p^2} $$ ...


2

Every non archimedean topology is totally disconnected. Hence every multiplicative group of non archimedean local field and its unit group is totally disconnected. since product of totally disconnected space is also totally disconnected., By the definition of idele, connected component of idele group is product of connected component of archimedean local ...


7

(The following is not meant to be serious mathematics.) In decimal there are $1000$ three place numbers. The probability that at the $N^{\rm th}$ decimal place of $\pi$ the last three figures enounce exactly the number $N$ therefore is ${1\over1000}$, and the probability that this does not happen is ${999\over1000}$. Assuming independence of the involved ...


1

Let's realize what you really want is: $$\lfloor y\rfloor (\lfloor y\rfloor +1)=y^2+O(y)$$ Let $f(y)=y(y+1)$. Then $f(y)-f(\lfloor y\rfloor) = f'(z) (y-\lfloor y\rfloor)$ for some $z\in [\lfloor y\rfloor, y]\subseteq (y-1,y]$. But $f'(z)=2z+1$ so $f'(z)= O(y)$ when $z\in (y-1,y]$, and $0\leq y-\lfloor y\rfloor <1$, so $f(y)-f(\lfloor y\rfloor) = O(y)$ ...


1

$$\frac{1}{2}[x/d]([x/d]+1)=\frac12\left(\frac xd+O(1)+1\right)\left(\frac xd+O(1)\right)=\frac{x^2}{2d^2}+\frac xdO(1)+O'(1)\\ =\frac{x^2}{2d^2}+O''\left(\frac xd\right).$$


2

This is a very broad area. Statistical tests can only rule out strings on the basis that they are "statistically unlikely to have been generated by a true random generator". Some keywords are NIST Tests, DieHard tests. Look at the Crypto and/or Theoretical Computer Science stackexchange sites and there will be posts tagged randomness or randomness testing. ...


0

the book Hardy wright theory of numbers has the equation you stated.author is probably Mordell and Hammond.


1

In this lemma $a_j$ gives a specific representant of $2j$ modulo $p$. This is the unique representant between $-\frac{p-1}{2}\leq a_j\leq \frac{p-1}{2}$. Just try for $p=11$ and $p=13$ : $$p=11 $$ $j=1,...,\frac{p-1}{2}=5$ you get : $$a_1=2=2\times 1$$ $$a_2=4=2\times 2$$ $$a_3=6=-5=2\times 3-11 $$ $$a_4=8=-3=2\times 4-11 $$ $$a_5=10=-1=2\times 5-11 ...


2

Integer solutions of a problem are essential in many areas. You wouldn't like that the number of persons to fit in the room be $13.5$, would you ? But besides this obvious pragmatism, it turns out that all research around integer solutions of equations, the so-called Number theory, ends-up in numerous beautiful (and difficult) extensions that make the ...


5

For the first question the answer is yes, and an upper bound is 16. We define a nearly good number to be such that the last digit is not the last digit of any of its proper divisors. We have the following result: $$ \text{Every nearly good number is the product of at most 4 prime numbers.}\ \ \ \ \ (*) $$ Hence every nearly good number (and also every good ...


3

Do you know the website Wolfram Alpha? You can use it to play around with equations, which will perhaps deepen your appreciation of Fermat's so-called last theorem (both words are problematic, but that's a different can of worms). Part of the reason whole numbers are important is because the problem becomes trivially simple if the requirement for integers ...


8

Clearly there are real and algebraic solutions. Just pick any value for $x$ and $y$ you want, and then solve for $z$ (possibly in the complex numbers). Since integers and rationals were the "first numbers" and Diophantine equations perhaps the "first equations" it makes some sense that we search for rational and integer solutions to Diophantine equations. In ...


3

Separate the set of primes $P$ into two sets $A_p,B_p$ by considering the partial products of $(1-1/2)(1-1/3)(1-1/5)\cdots$ with each factor of the form $1-1/p$ where the primes $p$ run through the sequence $2,3,5,\cdots$ of primes. We alternately go for partial products each at most $1/2,$ so that $A_p$ begins with $2$ [since $1-1/2\le 1/2$] and then $B_p$ ...


2

I think that this solution should be better than inclusion-exclusion, what about you take primes from factorization of n and run Eratosthene's sieve on $[a,b]$ using just these primes?


6

I must disagree with claims that "Algebraic Number Theory" is an algebraic study of anything-whatsoever, possibly including number theory, or, possibly "numbers", whatever the reference may be. That is, in genuine practice, it is "the theory of algebraic numbers", including "algebraic integers", including $p$-adic methods, including complex variables ...


3

Claim: $\displaystyle\;\frac{z}{y}$ is unbounded. Let $(x,y,z)$ stands for any integer solution for the equation $$x^2 + y^4 = 2z^4,\;\; z > 0\tag{*1}$$ Factorize above equation over Gaussian integers which is an UFD, we can conclude there are integers $u,v$ and $0 \le \epsilon < 4$ such that $$ x + iy^2 = i^\epsilon (1+i) (u+iv)^4\quad\text{ and ...


4

It is the study of number theory from an algebraic viewpoint. The methods of algebraic number theory are used to solve many problems in number theory. For example, the study of Gaussian integers sheds light on problem of which prime numbers are the sum of two squares.


0

This doesn't come close to a solution, but i thought it might be usefull to share this: Notice that a good number can not have a proper divisor that ends in a $1$ (except $1$ itself). Because if $x$ is divisible by a number $n$ that ends in a $1$ then $x$ and $x/n$ have their last digit in common. Also, (as hinted in the question) it is necessary for a ...


2

I find it easier to switch the roles of $d$ and $n/d$, so I write $$N(q,n) = \frac{1}{n}\sum_{d\mid n} \mu(d) q^{n/d}.$$ It is immediate that for $n = 1$ we have $N(q,1) = q$, so in that case the strict inequality does not hold. For $n > 1$, let $p$ be the smallest prime factor of $n$. If $n = p$, we have $N(q,p) = \frac{1}{p}(q^p-1) < ...


7

It's mostly the latter: the study of number theory from an algebraic viewpoint, just as analytic number theory is the study of number theory from the viewpoint of analysis. With algebraic number theory, it is often easier to solve equations that would be more difficult if not impossible with elementary methods. Algebraic number theory often deals with these ...


3

Yes. Just solve the equation $f(x) = f(y)$: $$2x^2 + 4x + 8 = 2y^2 + 4y + 8 \\ 2(x^2-y^2) + 4(x-y) = 0 \\ (x-y) \big( 2(x+y) + 4 \big) = 0 \\ x = y \vee x+y = -2$$ So $(x, y) \in E \iff x = y \text{ or } y = -x-2$.


0

The function is just $2(x+1)^2 + 6$. Clearly, $f(x)=f(y)$ iff $|x+1|=|y+1|$. In other words, the distance from $-1$ is the same for $x$ and $y$.


1

We have $$\left\lfloor \frac{x}{p}\right\rfloor =\frac{x}{p}+O\left(1\right) $$ then $$\sum_{p\leq x}\left\lfloor \frac{x}{p}\right\rfloor \log\left(p\right)=\sum_{p\leq x}\frac{x}{p}\log\left(p\right)+O\left(\sum_{p\leq x}\log\left(p\right)\right) $$ and for each $l\geq2 $ we have $$\sum_{p\leq x}\left\lfloor \frac{x}{p^{l}}\right\rfloor ...


3

You said in a comment: I conjectured the uniqueness only for numbers large enough. It would be interesting, which is the largest counterexample (I think there is a largest). I think your intuition is backwards here, and I think it will be instructive if I explain to you why; this is also why I was able to immediately guess that there would be ...


1

If instead of looking at $x=\frac{a^2}{b^2}$ you look at $x=-\frac{a^2}{b^2}$ you end up with $25b^4-a^4=n^2$ which has as an easy solution $a=2,b=1$. In fact the point $P=(-4,6)$ lies on the curve, and you can easily check that $2P$ has non-integral coordinates.


0

From $m$ consecutive numbers $n_0, n_0+1,\dotsc, n_0 + m-1$ with $$\omega(n_0 + \mu) \geqslant k$$ for $0 \leqslant \mu < m$ we find a sequence of $m+1$ consecutive numbers $n_\ast, n_\ast+1,\dotsc,n_\ast + m$ with $\omega(n_\ast + \mu) \geqslant k$ for $0 \leqslant \mu \leqslant m$ in the following way: If $\omega(n_0+m) \geqslant k$, we take $n_\ast ...


0

If $p\mid g$ then any power of $g$ is divisible by $p$, so you could never obtain $1\bmod {p^e}$. Or: From $g^m\equiv 1\pmod {p^e}$ with $m\ge1$ we see $g^{m-1}\cdot g+kp^{e-1}\cdot p=1$ for some integer $k$, so $\gcd(g,p)\mid 1$.


2

Yes you can prove this using simple tools. For example you can prove by induction that $\forall n\in\mathbb{N}$, $S_n$ is a ratio of an odd number and an even number, so it's not an integer.


1

since $m$ is a divisor of $2^p-1$ then there exists an integer $k$ such that $mk = 2^p-1$ now since $p \geq 3$ is prime then we know by fermat's last theorem that $$2^{p-1} \equiv 1 \pmod{p}$$ because obviously $\gcd(2,p)=1$ and so this implies that $p \mid2^{p-1} -1$ and hence there exists an integer $q$ such that $pq = 2^{p-1} -1$ and if we multiply by ...


0

Since $n$ is odd, we have $(3^n+5^n)\mid (3^{n^2}+5^{n^2})$ and thus $(n^2-1)\mid (3^{n^2}+5^{n^2})$. In other words, both $n$ and $n^2$ must belong to the set $$S=\{ m\in\mathbb{N} : (m-1)\mid (3^m+5^m)\},$$ which is represented by the sequence http://oeis.org/A234535 in the OEIS. It is therefore interesting to consider a (possibly simpler) question of ...


3

Consider the Wikipedia page for Algebraic Number Theory in other languages: Théorie algébrique des nombres Algebraische Zahlentheorie Teoria algebrica dei numeri Teoria algébrica dos números The exception that proves the rule is Spanish: Teoría de números algebraicos which starts by acknowledging the other form: "La teoría de números algebraicos o ...


0

Let $p$ be a prime $>5$ that is $\equiv 1 \pmod{4}$ and does not divide $3^5-2^5$, then let $$m=\frac{3^{5p}-2^{5p}}{3^5-2^5}.$$ $m$ is an integer since $3^5 \equiv 2^5 \pmod{3^5-2^5}$, so $3^{5p}\equiv 2^{5p}\pmod{3^5-2^5}$, so $3^5-2^5 \mid 3^{5p}-2^{5p}$. Now $$m-1 = \frac{3^{5p}-2^{5p}}{3^5-2^5}-1 \equiv \frac{3^5-2^5}{3^5-2^5}-1\equiv 0 \pmod{p}$$ ...


1

All Carmichael numbers not divisible by $3$ satisfy this condition. Alford, Granville Pomerance showed there are infinitely many Carmichael numbers, and their proof can be modified to show there are infinitely many that are congruent to $1 \mod 3$: more generally, Thomas Wright proved there are infinitely many Carmichael numbers $\equiv a \mod M$ for any ...


0

This is a consequence of Little Fermat: any integer $x\not\equiv 0\mod p$ satisfies the equation: $$a^{p-1}-1=0$$ As, if $p$ is odd, $a^{p-1}-1=\bigl(a^\tfrac{p-1}{2}-1\bigr)\bigl(a^\tfrac{p-1}{2}+1\bigr)$, each integer satisfies either $a^\tfrac{p-1}{2}-1=0$ or $a^\tfrac{p-1}{2}+1=0$, and each equation has $\dfrac{p-1}2$ solutions modulo $p$. Now we have ...


0

So suppose -1 is square modulo of an odd prime p. i.e for some integer x we have that $$x^{2} \equiv -1 \mod p$$ Evidently $\gcd(x,p)=1$, so applying Fermats Little Theorem gives $$(-1)^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1 \mod p $$ But this can only hold if $\frac{p-1}{2}$ is even, i.e $p=4k+1$ , some $k\in \mathbb{Z_{+}}$



Top 50 recent answers are included