Questions on more advanced topics of number theory. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

learn more… | top users | synonyms (1)

2
votes
2answers
107 views

Problem on higher order quadratic residuosity

For a prime $p$, we know cardinality of image of $Z_p$ under the map $f(x)=x^2$ is $\frac{p}{2}$. Is there any result for general polynomial like $f(x)=x^3+x$, $f(x)=x^3+x^2$ etc. ?
4
votes
1answer
180 views

Show $\underbrace{{111\cdots}1}_{{\small{p-1} \ 1's}}$ is divisible by $p$

What is the shortest proof to show $\underbrace{{111\cdots}1}_{{\small{p-1} \ 1's}}$ is divisible by $p$
3
votes
0answers
103 views

root of a unit in a real biquadratic field

Let $p_1$ and $p_2$ two primes numbers $\equiv 1\pmod 4$. If we note by $\varepsilon_m$ the fundamental unit of real quadratic field $\mathbb{Q}(\sqrt m)$, then how can be solved in ...
1
vote
1answer
138 views

Conditional equivalence of expression to cardinality of primes on square intervals

This is an exercise to show that $$\frac{\pi((x+1)^2) - \pi(x^2)}{\pi(x- \pi (x)) } \sim 1 $$ assuming the unproven hypothesis: $\displaystyle \pi (x^2, x^2+x^{2( \theta)}) \sim \frac{x^{2( ...
1
vote
1answer
50 views

What do you call a finite set of maps on $\mathbb{Z}$ that are closed and compatible with operations on $\mathbb{Z}$?

Let $S$ be the set of maps and $\phi,\psi \in S$. Let $x,y \in \mathbb{Z}$. Suppose that $\phi(x) * \psi(y) = \nu(xy)$ for some $\nu \in S$. Then what would you call such a system of maps? If that ...
4
votes
1answer
139 views

Let $n$ such that $\displaystyle{2^{n-2005}} | n!$

Let $n$ such that $\displaystyle{2^{n-2005}} | n!$ Prove that this number has at most $2005$ non-zero digits when written in base $2$.
8
votes
4answers
380 views

Is there a catalogue of solved Diophantine equations?

Is there a book, website or something else aiming to catalogue all or many of the Diophantine equations that have already been solved? I have two tiny books by Sierpiński in which he gives some of ...
11
votes
1answer
831 views

Fermat numbers are coprime

So today in my final for number theory I had to prove that the Fermat numbers ($F_n=2^{2^n}+1$) are coprime. I know that the standard proof uses the following: $F_n=F_1...F_{n-1}+2$ and then the ...
4
votes
1answer
93 views

Asymptotics for almost all $x$

Theorem 2.2 in Shparlinski 2006 says: For all positive integers $n\le x$ except possibly $o(x)$ of them, the bound $$M(x)\ll\frac{x}{\log x}\exp\left((C+o(1))(\log\log\log x)^2\right)$$ holds. ...
6
votes
1answer
435 views

How to show this ideal is not principal

I have been brushing up on cubic number fields. Specifically, let $s$ be a root of the polynomial $x^3 + x^2 + 3x + 17$, and consider $K = \mathbb{Q}(s)$; we have $\mathcal{O}_K = \mathbb{Z}[s]$, and ...
6
votes
0answers
208 views

Diophantine special problem

This is my another question on Diophantine equations. Prove the following great and special problem. Let $D$ and $k$ be positive integers and $p$ be a prime number such that $gcd(D, kp) = 1$. Prove ...
1
vote
1answer
82 views

How many natural multisets exist with a given sum?

Given natural number $n$, how many multisets are there which sum of their elements equals $n$? There is a recursive function which can give the value in $O(n^2)$, but is there a formula for that? ...
5
votes
0answers
279 views

Taxicab numbers.

I think most people know these numbers. Find $x,\ y,\ z,\ w$ such that $x^3 + y^3 = z^3 + w^3$ and $x,\ y,\ z,\ w$ are not equal to each other. The first is $1729$. I'm trying to figure out if ...
0
votes
2answers
1k views

Probability of an even sum

In a set of numbers there are 5 even numbers and 4 odd numbers. If two numbers are chosen at random from the set, without replacement, what is the probability that the sum of these two numbers is ...
4
votes
1answer
501 views

Diophantine Equations $z^2+2^y=3^x $ and $ z^2+4=5^n$

How one expect the possible values of $(x, y, z) = (0, 0,0), (1, 1, 1)$ and $(3, 1, 5)$ of the equation $3^x -2^y = z^2$ without by inspection. Why $n = 1$ and $3$ are valid for $5^n - 4 = z^2$. ...
4
votes
2answers
248 views

proof of a statement about the Diophantine equation $ax^2-by^2=c^2$

The Diophantine equation of the form a$x^2$ – b$y^2$ = $c^2$ with ab is not a perfect square in Z has infinitely solutions in N, provided by a particular non-trivial solution in set of N. I have ...
5
votes
0answers
135 views

Density of products of a certain set of primes

I have an infinite set S of prime numbers with relative density 0 (that is, $\lim_ns_n/p_n=\infty$ with $S=\{s_1,s_2,\ldots\}$ and $s_1 < s_2< \cdots$). I would like to find the size (in some ...
1
vote
1answer
101 views

A pattern in distribution of near-primes less than $2^n$

Let $\pi_k(2^n)$ be the number of almost-primes (numbers with k factors including repetitions) less than $2^n$. I noticed that for large values of n and values of k near n, a sequence $\{\pi_k\}$ ...
4
votes
2answers
291 views

Equivalence of quadratic forms over p-adic fields.

There is a theorem that states that two quadratic forms over $\mathbb{Q}_p$ are equivalent iff they have the same rank, discriminant and the same $\epsilon$ invariant. (The last is defined as ...
1
vote
1answer
120 views

Between 1 and $n!$, how many elements will be there which divides $n!^2$

Between 1 and $n!$, how many elements will be there which divides $n!^2$. How to dervive to the formula or any algorithm. I tried doing different combinations but not arriving to exact solutions.
3
votes
2answers
175 views

Number of solutions to $a_1 + a_2 + \dots + a_k = n$ where $n > 0$ and $0 < a_1 \leq a_2 \leq \dots \leq a_k$ are integers.

I know how to find the number of solutions to the equation: $$a_1 + a_2 + \dots + a_k = n$$ where $n$ is a given positive integer and $a_1$, $a_2$, $\dots$, $a_n$ are positive integers. The number ...
3
votes
2answers
664 views

“GCD” of any two real numbers

This isn't really a GCD question, because GCD is only defined for integers. I'm interested in the the existence of a common divisor of any two non-zero real numbers. In other words can you prove or ...
2
votes
3answers
371 views

Legendre Symbol Problem

I am doing revision for my number theory exam and I am stuck on the following question. Let $x$ be an even integer. Show that every prime divisor $p$ of $x^4 + 1$ satisfies $\big(\frac{-1}{p}\big)$ = ...
8
votes
2answers
934 views

GrossOne? The arXiv blog's pick of the day.

The arXiv blog having chosen GrossOne for its daily pick of today, I read the arXiv paper concerned, and posted a comment there. The arXiv blog used to be quite high profile as these things go. Is ...
3
votes
2answers
302 views

solution of the Diophantine equation of the form $(2^n)^x + p^y = z^2 $

Can we find solutions of Diophantine equations of the form : $$(2^n)^x + p^y = z^2 $$ where $k, x, y, z$ and $n$ are positive integers. -Richard Simson
4
votes
4answers
640 views

Group theory proof of Euler's theorem ($a^{\phi(m)} \equiv 1\mbox{ }(\mbox{mod }m)$ if $\gcd(a,m)=1$)

From A Classical Introduction to Modern Number Theory by Ireland and Rosen, page 33: Corollary 1 (Euler's Theorem). If $(a,m) = 1$, then $a^{\phi(m)} \equiv 1\,(m)$. Proof. The units in ...
3
votes
2answers
334 views

Finding the unit digit of the following expressions, A and B.

Let A be:$${2013}^{{2012}^{{2011}^{2010.....}}}$$ This, goes, on, till, $3^{{2}^1}$ Let B be:$${2012}^{{2011}^{{2010}^{2009.....}}}$$ This, goes, on, till, $3^{{2}^1}$, For A , I did this, Let ...
2
votes
2answers
41 views

questions about Jacobosthal number.

Jacobosthal number is defined by $J_n=J_{n-1}+2J_{n-2},J_0=0,J_1=1$. The leading part of the sequence is $0,1,1,3,5,11,21,43,85,\dots\;$. How to show that this number is the number of numbers which is ...
0
votes
2answers
66 views

if $a,b \in \mathbb{Z}$, $a>b>0$, $b<2^n$, then in the Euclidean algorithm for $\gcd(a,b)$ the number of steps(divisions) is not more than $2n$.

I'd love your help with proving that if $a,b \in \mathbb{Z}$, $a>b>0$, $b<2^n$, then in the Euclidean algorithm for $\gcd(a,b)$ the number of steps(divisions) is not more than $2n$. I tried ...
4
votes
4answers
314 views

Find the sum of p+q?

If p = last non zero digit of 96! and q = Remainder(121212....300 times / 99 ) Find the value of p+q. Thanks in advance. How we can get the value from such ...
8
votes
5answers
324 views

Traveling between integers- powers of 2

Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed. Consider the integers. We can only travel directly between two ...
1
vote
1answer
123 views

constructing finite extensions with prescribed ramification

How does one construct (or show the existence at least) of a finite field extension $L$ of a complete discrete valuation field $K$ which ramifies totally over precisely one given prime ideal $p$ in ...
2
votes
2answers
275 views

Application of prime number theorem

In the following I am referring to a small argument made in "A counterexample to Borsuk's conjecture" by Jeff Kahn, Gil Kalai (see http://arxiv.org/abs/math.MG/9307229) In this paper the authors bound ...
4
votes
2answers
125 views

Property of a sequence involving near-primes

Let $p_k(m)^2:=$ the square of $m^{th}$ number containing k prime factors, including repetitions. Empirically for smallish numbers and as a conjecture, it appears that for every m and sufficiently ...
4
votes
1answer
185 views

Three step proof of the divergence of $\sum_{p\in \mathbf{P}} \frac{1}{p}$

In my Number Theory skript it says: By showing that there are at most $(1+\frac{\log n}{\log 2})^{\pi(x)}$ numbers with $m\le n$ which are divisible only by prime numbers $p\le x$. By showing that ...
2
votes
2answers
126 views

What am I supposed to do in “If a and b are natural numbers, and ab=1, then a=1 and b=1”?

I'm currently starting a number theory book. On its exercise, there's: Prove: If $a,b \in \mathbb{N}$ and $ab=1$, then $a=1$ and $b=1$. Here's one proof I just did: Since $ab=1$, $a=\frac{1}{b}$. ...
1
vote
1answer
102 views

How to show $\pi (2n) \ge \log \binom{ 2n }{ n} / \log 2n$?

Proposition: $\pi (2n) \ge \dfrac{\log \binom{ 2n }{n} }{\log 2n}$ Since this is a follow up proposition to this one: How can we show that $\operatorname{ord}_{p}\left(\binom{2n}n\right) \le ...
1
vote
1answer
89 views

How can we show that $\operatorname{ord}_{p}\left(\binom{2n}n\right) \le \frac{\log 2n}{\log p}$

How can we show that $$\operatorname{ord}_{p}\left(\binom{2n}n\right) \le \frac{\log 2n}{\log p}$$ where $p$ is a prime number and $n$ is a natural number My attempt: $$2^{n} \le \prod ...
30
votes
3answers
444 views

Do we really know the reliability of PrimeQ[n] (for $n>10^{16}$)?

The algorithm Mathematica uses for its PrimeQ function is described on MathWorld. That web page says PrimeQ uses, "the multiple ...
2
votes
1answer
273 views

Form of minimal integral Weierstrass equation for elliptic curve over $Q$ with good reduction at $2$ and $3$.

If $E$ is an elliptic curve over $\mathbb{Q}$ which has good reduction at $2$ and $3$, is it always possible to find a minimal integral Weierstrass equation for $E$ of the form $y^2 = x^3 + Ax + B$ ...
6
votes
2answers
177 views

How can we show that $\pi (x+y) - \pi(y) \le \frac{1}{3} x + C$ using the sieve of eratosthenes?

How do we show that For $x,y \ge 0$ real numbers, there exists a constant C suchthat: $$\pi(x+y)-\pi(y) \le \frac{1}{3}x+C$$ Where $\pi(.)$ denotes thes prime counting function, is true? the ...
9
votes
4answers
868 views

(Simple?) applications of Class Field Theory?

Does anyone know any simple/nice applications of class field theory? I would really like to find one related to diophantine equations, but anything you got would be good. Thanks
2
votes
1answer
126 views

Dirichlet Series Coefficients from Quadratic Euler Products

Given an Euler product of the form \begin{align} L(s) = \prod_{p}(1 - a_{p} p^{-s} - b_{p} p^{-2s})^{-1} \end{align} where $a_n$ and $b_n$ are not necessarily a multiplicative arithmetic functions of ...
9
votes
1answer
2k views

Chinese Remainder theorem with non-pairwise coprime moduli

Let $n_1,...,n_k \in \mathbb{N}$ and let $a_1,...,a_k \in \mathbb{Z}$. How to prove the following version of the Chinese remainder theorem (see here): There exists a $x \in \mathbb{Z}$ satisfying ...
5
votes
1answer
92 views

powers of $\frac{1+\sqrt a}2$

For any a which is not a perfect square, let $x=\frac{1+\sqrt a}2$. $x^n$ can be written uniquely as $b_nx+c_n$, where b and c are rational. Apart from $a=0, a=1, a= 1 \pm 2^m$ for $m>2$, are ...
1
vote
1answer
66 views

Is it possible to store an integer in sub-logarithmic space?

The most intuitive method of representing an integer is in unary. For example, 10 can be represented as 0000000000, ----------, etc. This requires O(n) space. The most common method is slightly more ...
5
votes
3answers
691 views

how many zeroes does 2012! have at the end? [duplicate]

Possible Duplicate: How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes? How many zeroes does $2012!$ end with? My idea is: 402 zeroes ...
6
votes
1answer
232 views

An elegant non-technical account on the work of Joseph Fourier.

It would seem difficult for a naive person to understand the beauty of work done by Fourier. So as far as I know, one can use the Fourier transforms, analysis and series to apply them for heat ...
1
vote
2answers
46 views

Difficulty showing “and”

I'm trying to show that $a^2 \equiv b^2 \mod p$ implies that $a \equiv b \mod p$ and $a \equiv -b \mod p$, where $p$ is prime. Since $a^2 - b^2 \equiv 0 \mod p$, I know that $(a + b)(a - b) \equiv 0 ...
7
votes
2answers
1k views

How to prove $\phi(mn) > \phi(m)\phi(n)$ if $(m,n) \ne 1$

I need to prove that $$\phi(mn) > \phi(m)\phi(n)$$ if $m$ and $n$ have a common factor greater than 1. I have read up on the case where $m$ and $n$ are relatively prime, then ...