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)

7
votes
0answers
149 views
+50

Minimal distance limit problem

Consider a square $\{(x,y): 0\le x,y \le 1\}$ divided into $n^2$ small squares by the lines $x = i/n$ and $y = j/n$. For $1\le i \le n$, let $x_i = i/n$ and $$d_i = \min_{0\le j\le n} \left| ...
1
vote
1answer
25 views

Proving Combinatorics Statements are equivalent [on hold]

How can I prove that $$\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}$$ Based on this how can I then prove that $$ \sum_{k=1}^{m}\binom{n}{k}\binom{n-k}{m-k}=2^{m}\binom{n}{m}$$ Thank you ...
1
vote
3answers
77 views

Find the 44th digit of a 80 digit number if number is divisible by 13

N is an 80-digit positive integer (in the decimal scale). All digits except the 44th digit (from the left) are 2. If N is divisible by 13, find the 44th digit ? P.S: This isn't a homework question. ...
0
votes
0answers
14 views

Parametrization of solutions of diophantine equation

The issue I discussed in this thread. Parametrization of solutions of diophantine equation $x^2 + y^2 = z^2 + w^2$ Generally speaking at the forum often ask a question about this equation. So I ...
1
vote
1answer
20 views

To solve the system of Diophantine equations.

I decided to compile a single task and to record such a system. $$\left\{\begin{aligned}&xt+yw=az^2\\&xw-yt=br^2\end{aligned}\right.$$ $a,b - $ integers that are the problem. It is clear ...
-1
votes
0answers
29 views

value for x in product 165432078*1009612= 167022211x3376

I have the next product: $$165432078*1009612= 167022211x3376$$ How can I now which the value for $$x$$ is?
5
votes
3answers
145 views

Show that there is no integer n with $\phi(n)$ = 14

I did the following proof and I was wondering if its valid. It feels wrong because I didn't actually test the case when purportedly n is not prime, but please feel free to correct me. Assume there ...
3
votes
1answer
62 views

Euler's function $\phi$: Values such that $\phi(n)=8$, $\phi(n)=14$

Let $\phi(n) $ be Euler's Totient Function Let us consider $$ |\{ n \in \mathbb{N} : \phi (n) = 8 \} | = 5, $$ and $$ |\{ n \in \mathbb{N} : \phi (n) = 14 \} | = 0. $$ How would I go about ...
1
vote
2answers
29 views

Ideal as kernel of a homomorphism

Consider the ring $\mathbb{Z}[i]$ of Gaussian integers. The principal ideal $(1+i)$ is maximal ideal in this ring. Since ideals are kernels of some homomorphisms, I would like to see a homomorphism ...
2
votes
0answers
15 views

A bound on number of elements less than $n$ of a $B_2[g]$ sequence

Let $S \subset \mathbb{N}$. We say $S$ is of type $B_2(g)$ if the number of representation of the form $n = s_1 + s_2 \ (s_1 \leq s_2)$ is bounded by $g$ for every $n \in \mathbb{N}$. Let $S(n)$ be ...
36
votes
1answer
854 views

Estimate for $n$th prime

A good approximation I have found for $p_{n}$ is \begin{align} \int_{2}^{n}\log (x \log (x \log (x)))\ dx\\ \end{align} and seems to be a better estimate than $n \log (n)$. The error term seems to ...
5
votes
2answers
48 views

Determine all units in $\mathbb{Z}[\omega] := \{a+b\omega\mid a,b\in\mathbf{Z}\}$ where $\omega = \frac{-1 + i \sqrt{3}}{2}$

My attempt: $N(a + b\omega) = (a + b \omega)(a - b \omega) = a^2 + \omega^2 b^2$ I'm stuck here. Is my approach correct?
8
votes
2answers
419 views

Help to understand a proof by descent?

I am trying to understand the proof in Carmichaels book Diophantine Analysis but I have got stuck at one point in the proof where $w_1$ and $w_2$ are introduced. The theorem it is proving is that the ...
0
votes
0answers
16 views

Proof of Chevalley–Warning theorem

How to prove Chevalley–Warning theorem (http://en.wikipedia.org/wiki/Chevalley%E2%80%93Warning_theorem) by using Fulton's trace formula (#$|X(\mathbb{F}_p)| \equiv \sum (-1)^i Tr(Frob_p|H^i(X, ...
1
vote
1answer
13 views

Definitions of valuations in terms of totally ordered group

Wikipedia gives a definition of valuations involving abelian totally ordered groups. So far I have only seen valuations taking values in the real numbers. Is there a reason for this generalization?
0
votes
1answer
37 views

$f(x)=x^2-a \in \mathbb{Z}[x]$ - show propositions

Let $f(x)=x^2-a \in \mathbb{Z}[x]$. $$p \in \mathbb{P}, p \neq 2, p^2 \nmid a$$ The equation $f(x)=0$ If $p \mid a $, the equation has no solution in $\mathbb{Q}_p$ Let $p \nmid a$. The ...
1
vote
1answer
30 views

Parametrizing solutions of diophantine $8x^2 + y^2 = z^2$ gone wrong. Where's the mistake?

So I have $$ 8x^2 + y^2 = z^2. $$ Dividing both parts by $z$ yields $$ 8X^2+Y^2 = 1, $$ where $X$ and $Y$ are rational. Point $(0, -1)$ is on the ellipse, so I parametrize with $(X, tX - 1)$, where ...
5
votes
0answers
144 views

Primes of the form $\frac{n^2-n+4}{2}$ satisfy Hardy-Littlewood analogue?

Let $n,a,b$ be positive integers with $a<b$. Consider primes of the form $f(n)=\dfrac{n^2-n+4}{2}$. Let $C(a,b)$ denote the amount of primes of the form $f(n)$ between (and including) $f(a)$ and ...
10
votes
3answers
404 views

$\sum_{p \in \mathcal P} \frac1{p\ln p}$ converges or diverges?

We will denote the set of prime numbers with $\mathcal P$. We know that the sum $\sum_{n=1}^{\infty}\frac1n$ and $\sum_{n=2}^{\infty}\frac1{n\ln n}$ diverges. It is also known that $\sum_{p \in ...
1
vote
1answer
33 views

For which $a>0$ does the equation $x^2+y^2+z^2=a$ have a solution in $\mathbb{Q}_2$?

We want to check for which $a>0$ we have that the equation $x^2+y^2+z^2=a$ has a solution in $\mathbb{Q}_2$. $x^2+y^2+z^2=a$ has a solution in $\mathbb{Q}_2$ for $x \in \mathbb{Z}_2^{\star}, y ...
1
vote
1answer
40 views

Parametrization of solutions of diophantine equation $x^2 + y^2 = z^2 + w^2$

I need integer solutions of $x^2 + y^2 = z^2 + w^2$ parametrized. Can it be done? Thanks.
1
vote
1answer
541 views

How Many Points between two points?

Given two points $A$ and $B$ on the $X-Y$-plane, I have to output the number of the lattice points on the segment $AB$. Note that $A$ and $B$ are also lattice point. Those who are confused with the ...
2
votes
1answer
83 views

Find all integer solutions of $x^4 + 2x^3 + 2x^2 + 2x +5 = y^2$

Find all integer solutions to $x^4 + 2x^3 + 2x^2 + 2x +5 = y^2$. I'm in a dead end. I've transformed the expression in the following state: $(x^2+1)(x+1)^2 = y^2 -4$ I couldn't see anyway in ...
3
votes
1answer
82 views

$\sqrt{m_1}+\sqrt{m_2}+ \cdots + \sqrt{m_n}$ is Irrational

If $m_1 , m_2, \cdots m_n$ are natural numbers where at least one of them is not a perfect square, then how do I prove that the sum $$\sqrt{m_1}+\sqrt{m_2}+ \cdots + \sqrt{m_n}$$ is irrational? I'm ...
1
vote
1answer
25 views

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.. I am totally lost; at first I thought this could be done by induction, but unfortunately this is not possible (at least I ...
1
vote
2answers
139 views

Two Problem: find $\max, \min$; number theory: find $x, y$

Find $x, y \in \mathbb{N}$ such that $$\left.\frac{x^2+y^2}{x-y}~\right|~ 2010$$ Find max and min of $\sqrt{x+1}+\sqrt{5-4x}$ (I know $\max = \frac{3\sqrt{5}}2,\, \min = \frac 3 2$)
1
vote
0answers
45 views
+100

On a congruence for the number of finite topologies

I am making search about "On a congruence for the number of finite topologies". I have found a paper. I guess it is written in Russian. How can I find English version of this paper ? I am also ...
1
vote
1answer
44 views

Show that $-1=\sum_{0}^{\infty} (p-1)p^i$ in $\mathbf{Q}_p$

To show that in the field $\mathbb{Q}_p$, where $p$ is a prime, it holds that: $$-1=\sum_{0}^{\infty} (p-1)p^i$$ I did the following: It suffices to show that: $\left|\sum_0^N (p-1)p^i+1 \right|_p ...
0
votes
1answer
45 views

A fast method for factorizing $2^p-1$

I know that $\forall{d,n\in\mathbb{N}}:d|n\implies2^d-1|2^n-1$. Now, suppose that $n$ is prime - is there any fast algorithm for finding a divisor of $2^n-1$? By "divisor", I am referring to a ...
0
votes
3answers
54 views

Inductive step in proof of Freshman's Dream

I am trying to prove that for $K$ a field of characteristic $p$ prime, $q$ a power of $p$ and $x,y$ in $K$, $$(x+y)^q=(x^q + y^q).$$ I have the base case, and now I am trying to do the inductive ...
2
votes
2answers
1k views
1
vote
1answer
80 views

Find all natural sequences $a_n=a_{a_{n-1}}+a_{a_{n+1}}$

Find all natural sequences for which holds $$a_n=a_{a_{n-1}}+a_{a_{n+1}}$$ a) for all natural numbers $n\ge 2$ b) for all natural numbers $n\ge 3$ I tried to do something with the characteristic ...
1
vote
1answer
26 views

Discrete Logarithm Problem

Question: Discrete Logarithm Problem: Let $g$ be a primitive root for $F_{p}$. Suppose that $x = a$ and $x = b$ are both integer solutions to the congruence $g^{x} \equiv h \pmod{p}$. Prove that $a ...
0
votes
1answer
48 views

If $a^2$ divides $b^3$, then $a$ divides $b$.

I want to prove or provide a counterexample to the following statement: $a^2|b^3 \Rightarrow a|b$. I know that $a^k|b^k \Rightarrow a|b$. My thought is that, e.g in the case of $k = 3$, where we ...
1
vote
0answers
79 views

What does $p\mathbb{Z}_p$ mean?

I am looking at Hensel's Lemma: Let $F(x)=a_0+a_1x+ \dots + a_n x^n \in \mathbb{Z}_p[x]$. We suppose that there is a $p$-adic number ($p>2$) $\alpha_1 \in \mathbb{Z}_p$, such that: $$F(\alpha_1) ...
1
vote
1answer
37 views

Question about the proof of Hensel's Lemma

Hensel's Lemma: Let $F(x)=\alpha_0 + \alpha_1 x+ \dots + \alpha_n x^n \in \mathbb{Z}_p[x]$. We suppose that there is a $p$-adic $a_1 \in \mathbb{Z}_p$ such that $$F(a_1) \equiv 0 \mod p ...
0
votes
1answer
32 views

Integer factorization simplification

I found a small improvement to the brute force algorithm for the Integer Factorization. Please tell me if there is a point to investigate it more or there are better similar ideas. I found that if ...
3
votes
2answers
83 views

Inverse limit of $\mathbb{Z}/n\mathbb{Z}$

I know that this is well-known fact that $$\lim\limits_\leftarrow\mathbb{Z}/n\mathbb{Z}=\prod\limits_p\mathbb{Z}_p,$$ however I don't know the rigorous proof of this. Can anyone give me the ...
0
votes
1answer
29 views

Closed Form of n(mod7) [on hold]

For an integer n,what is the closed form as a function of n, if it exists, of n(mod7)={0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,...,n(mod7)}? The closed form of n(mod8) uses trigonometric ...
4
votes
1answer
37 views

There is a primitive $m^{th}$ root of unity in $\mathbb{Q}_p$ $\Leftrightarrow m \mid (p-1)$

After Hensel's Lemma there is the following proposition in my notes: If $p$ is a prime and $m \in \mathbb{N}$ then there is a primitive $m^{th}$ root of unity in $\mathbb{Q}_p$ $\Leftrightarrow m ...
1
vote
1answer
37 views

pth root of unity in $p$-adic field

It is well known that $\mathbb{Q}_p(\mu_n)$ is a totally ramified extension of degree $(p-1)p^n$ if $\mu_n$ is a primitive $p^n$th root of unity. However how true is this statement for a finite ...
0
votes
2answers
15 views

Finding $2m+1=2\alpha k+\alpha^2$ quickly

Given some positive integer $m$ I'm looking for all solutions $\alpha,k>0$ to $2m+1=2\alpha k+\alpha^2$ with $0<k^2<2m.$ Right now I'm finding these by looping over each of these possible $k$ ...
1
vote
1answer
45 views

On the prime number theorem in shorts intervals

In 1988 Heath-Brown (" The number of primes in a short interval ", J. reine angew. Math. 389, 22-63) proved this theorem: Let $\varepsilon\left(x\right)\leq\frac{1}{12}$ be a non-negative function ...
0
votes
0answers
12 views

The equation $P(X,Y)$ has a solution in $\mathbb{Q}_p$

Proposition Let $P(X,Y) \in \mathbb{Z}[X,Y]$. The following propositions are equivalent: The equation $P(X,Y)$ has a solution in $\mathbb{Q}_p$. For each $n \geq 0$ the equation $P(X,Y)$ has a ...
2
votes
3answers
55 views

Counting the number of $\mathbb{F}_q$ points on a homogeneous polynomial

This is an area of number theory that I am not too familiar with and I would appreciate any assistance! Let $\mathbb{F}_q$ be a finite field of $q$ elements with characteristic not 2 or 3. I have the ...
3
votes
1answer
31 views

$GL_2(\mathbb{Q}_p)$ and $GL_2(\mathbb{Z}_p)\cdot\mathbb{Q}_p^\times$

I am confused by a question, which is probably of school level. In some papers I have seen an induction from the group $GL_2(\mathbb{Z}_p)\cdot\mathbb{Q}_p^\times$ to the group $GL_2(\mathbb{Q}_p)$, ...
0
votes
0answers
60 views

Idele for a rational number $q=\frac{63}{550}$ [on hold]

Wikipedia, in its article "p-adic number", has taken an arbitray number $x= \frac{63}{550}$ to show the p-adic absolute value with respect to different primes. Obviously, the p-adic absolute value is ...
4
votes
0answers
32 views

Can we find the GCD of two polynomials in $\mathbb Q[x]$ by representing the coefficients as vectors?

Can we find the GCD of two polynomials in $\mathbb Q[x]$ by representing the coefficients as vectors? For example: $f=x^5+3x^4+x^3+4x^2+1$, and $g=x^5+3x^4+4x^3+3x+1$ Can we represent these ...
3
votes
1answer
49 views

Solving A Certain Diophantine Equation

I am stack on finding the solution of the diophantine equation: $d(2^{k+1}-1)-b^2(2^{k+1}-2)=1$. where $k\geq 1$ and $b^2>d$ for $b$ an odd composite integer. Is there a solution to this ...
2
votes
0answers
35 views

Short intervals with all numbers having the same number of prime factors

How to prove that for some $k, n_0$, for all $n \ge n_0$ it is never the case that all integers in $\{n, n+1, \dots, n + \lfloor (\log{n})^k \rfloor\}$ have exactly the same number of prime factors ...