Tag Info

Hot answers tagged

15

"I am interested in Theorem statement, corollary, or Trick or Logic which solves this problem within one minute." Ok, so perhaps you are looking at Fermat's Little Theorem, where $n$ is prime, and $a$ is not a multiple of $n$: $$a^{n-1}\equiv1\ mod\ n$$ So in your case of $$a^{24}\equiv6a+2\ mod\ 13$$ Therefore using Fermat's Little Theorem: ...


9

If we don't have any restriction to $F$ (besides -I guess- that $F$ is a natural number) then $F=0,1,2$ produce rational numbers ($0,0,1$, respectively). Your proof is valid for $F\ge 3$ as you are assuming $3|F!$ in step (5).


8

Hint: $64\times 65 \dots \times 70 \equiv -7\times -6 \dots \times -1$ To break it down further try


8

If $3\mid a$ we are done, if not either $a = 1 \pmod 3$ or $a = 2 \pmod 3$, either case $a^2+2 = 0 \pmod 3$.


7

I will do exactly the same thing. I just finished my degree in mathematics but in our department there is not a single course of Number Theory, and since I will start my graduate courses in October I thought it will be a great idea to study Number Theory on my own. So, I asked one of my professors, who is interested in Algebraic Geometry and Number Theory, ...


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$.


6

By Fermat's little theorem, $a^{24} = (a^{12})^2 \equiv 1^2 = 1 \pmod{13}$ (assuming $13\nmid a$, which is the case here).Thus you're really trying to solve $1\equiv6a+2\pmod{13}$, which is much easier.


5

This time I let the target Carmichael number be the least common multiple of the numbers from $1$ to $w.$ This is more efficient in terms of the number of divisors. The Superior Highly Composite Numbers and the Colossally Abundant Numbers share the main property of this LCM, which is that the exponent of some prime $p$ is proportional to $1/ \log p.$ As a ...


5

The solutions $a^{2} \equiv 1 $ mod $29 \equiv (a-1)(a+1) \equiv 0$ mod $29$. Since $29$ is prime, it follows that $a-1 \equiv 0$ mod $29$ or $a+1 \equiv 0$ mod $29$. So we need to solve $2x \equiv 1 $ mod $29$ or $2x \equiv -1 \equiv 28$ mod $29$. The first has solution $15$, the second $14$.


5

Alternatively, we first prove the following claim. Let $x,y,p,q\in\mathbb{N}$ be such that $\gcd(p,q)=1$ and $x^p=y^q$. Then, there exists $u \in \mathbb{N}$ such that $x=u^q$ and $y=u^p$. Proof: As $\gcd(p,q)=1$, there exist $r,s\in\mathbb{Z}$ such that $pr+qs=1$. Hence, ...


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 ...


4

One of the best is An Introduction to the Theory of Numbers by Niven, Zuckerman, and Montgomery.


4

You can write the numerator as $$a^3-a\mod 3.$$ Fermat's little theorem says all $a$ are congruent to $a^3$ mod $3$, hence the numerator is divisible by $3$.


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}$.


4

Rewrite this as $$3^z-4=5^x7^y$$ Then we see, because $x>0$, that $$3^z-4\equiv 0\mod 5 \iff 3^z\equiv -1\mod 5$$ so $z=2j$ is even. Then we have $(3^j-2)(3^j+2)=5^x7^y$. Since the gcd of these two divides $4$--because $(3^j-2)+(3^j+2)=4$--we have that they are coprime (any larger factor would then be a factor of $5^x7^y$ which is odd), i.e. one ...


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 ...


4

To check that $x^{100} - 1$ is divisible by $1000$, it will suffice to check that it is divisible by $8$ and $125$. For each of these, you can use Euler's theorem, which will tell you that $x^{p^{k-1}(p-1)} \equiv 1 \pmod {p^k}$, where $p$ is a prime not dividing $x$. In this particular case, you have $x^{4} \equiv 1 \pmod{8}$ (so in particular $x^{100} ...


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!


4

Let $d=(a,b)$ be the g.c.d. of $a$ and $b$. We will show that $a+b=d^2$. Write $a=a_1d$ and $b=b_1d$. You also have $(a_1,b_1)=1$. We thus have $$\frac{1}{a}+\frac{1}{b}=\frac{1}{d}\left(\frac{1}{a_1}+\frac{1}{b_1}\right)=\frac{1}{c}$$$$\frac{a_1+b_1}{a_1b_1}=\frac{d}{c}$$ Observing that $(d,c)=1$ and $(a_1+b_1,a_1b_1)=1$, we get that $a_1+b_1=d$ and ...


4

In the real numbers, a method of finding a solution to a quadratic equation is to complete the square. This would involve adding and subtracting $(b/2)^2$. $b=3$ in your case, and remember that $1/2 = 19 \mod 37$. Specifically notice: $$(x+3 \cdot 19)^2 \equiv x^2 + 2\cdot 3 \cdot 19 x + (3 \cdot 19)^2$$ $$\equiv x^2 + 3x + (20)^2 \mod 37$$ Note that $3 ...


4

$$\frac{26+11}{13}=2+\frac{1}{\frac{13}{11}}=2+\frac{1}{1+\frac{1}{\frac{11}{2}}}=2+\frac{1}{1+\frac{1}{5+\frac{1}{2}}}$$


4

When you’re speaking of the $p$-adic domain, the concepts of “real” and “complex” don’t make sense. Those concepts relate only to the archimedean metric on $\Bbb Q$. You’re correctly observing that every root of the $n$-th cyclotomic polynomial is complex, but what about $X^6-5$? Irreducible, all the roots are equivalent in a Galois-theoretic viewpoint, and ...


3

Well if $q$ is also rational, i.e. $q\equiv 3\mod 4$ is a rational prime, then it's really easy, you just have $$\Bbb Z[i]/(q)=\{a+bi : 0\le a,b<q\}.$$ You already knew that, but I like to be complete. If $q=1+i$, then note that $(1+i)(1-i)=2$ so $2\equiv 0\mod (1+i)$ so $$\Bbb Z[i]/(1+i)\subseteq \{a+bi : 0\le a,b\le 1\}$$ Since $1= (1+i)+i$ ...


3

$$x^2+3x+7\equiv x^2+40x+400+(-393)\equiv 0$$ $$\iff (x+20)^2\equiv 393\equiv 23\pmod{\! 37}$$ Use Quadratic Reciprocity: $$\left(\frac{23}{37}\right)=\left(\frac{37}{23}\right)=\left(\frac{14}{23}\right)=\left(\frac{7}{23}\right)\left(\frac{2}{23}\right)$$ $$=-\left(\frac{23}{7}\right)=-\left(\frac{2}{7}\right)=-1$$ In general, you can always complete ...


3

Hint: We have $p-1\equiv -1\pmod{p}$, $p-2\equiv -2\pmod{p}$, $p-3\equiv -3\pmod{p}$, and so on up to $\frac{p+1}{2}\equiv -\frac{p-1}{2}\pmod{p}$. It follows that $$(p-1)!\equiv (-1)^{(p-1)/2}\left(\left(\frac{p-1}{2}\right)!\right)^2\pmod{p}.$$ Now use Wilson's Theorem.


3

Got a reference on MO; see http://mathoverflow.net/questions/210144/number-of-primes-one-larger-than-divisors-of-a-fixed-number-which-is-lcm-of-1-2#comment520981_210144 and http://www.math.drexel.edu/~eschmutz/PAPERS/lambda.pdf In Theorem $1$ on the first page of the Erdos-Pomerance-Schmutz article, they announce the existence of a constant $c$ and a ...


3

You were correct. $$x^2\equiv 24\pmod{\! 60}\iff \begin{cases}x^2\equiv 24\equiv 0\pmod{\! 3}\\ x^2\equiv 24\equiv 0\pmod{\! 4}\\ x^2\equiv 24\equiv 4\pmod{\! 5}\end{cases}$$ $$\iff \begin{cases}x\equiv 0\pmod{\! 3}\\ x\equiv 0\pmod{\! 2}\\ x\equiv \pm 2\pmod{\! 5}\end{cases}$$ If and only if at least one of the two cases holds: $1)$ $\ x\equiv 0\pmod{\! ...


3

Edit: (June 29th 2015) I misread this question as asking for sum of $1/|\mathfrak{p}|^2$ over those elements of $\mathbb{Z}[\alpha]$ that are irreducible over $\mathcal{O}_K$. This is clearly not what the question asks, I am just use to irreducibility in a number field being defined with respect to the ring of integers, so I must have skipped some words. ...


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 ...


3

That is equivalent to: $$ 3x^2+6x+39\equiv 0\pmod{19} $$ or to: $$ x^2+2x+13\equiv 0\pmod{19} $$ or to: $$ (x+1)^2 \equiv 7\pmod{19}. $$ Since $\left(\frac{7}{19}\right)=-\left(\frac{5}{7}\right)=-\left(\frac{2}{5}\right)=+1$ and $19$ is a prime of the form $4k-1$, a square root of $7$ is given by $$ 7^{\frac{19+1}{4}}\equiv 7^{5}\equiv 11\pmod{19} $$ and ...



Only top voted, non community-wiki answers of a minimum length are eligible