Tagged Questions

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
1answer
35 views

Average order of Eulers totient function squared

I was wondering if one has a nice asymptotic formula for the sum $$\sum_{n\le x} \phi(n)^2$$ and if so, how does one calculate it. I know that one has $\sum_{n\le x} \phi(n) = ...
0
votes
1answer
34 views

Is $r_2$ a uniformly at random value in $Z_n$, where $r_2=r_1 . m$

Let $m$ be an arbitrary value in $Z_n$, where n is RSA modulo (n=p.q, where p and q are large primes). Then have: $r_2=r_1 . m$, where $r_1$ is a value chosen uniformly at random : $r_1\in Z^*_n$. ...
1
vote
0answers
30 views

Dirichlet convolution [duplicate]

Can anyone give a proof for commutativity and associativity of dirichlet convolution?? Thanks.
3
votes
1answer
141 views

Number theory / Group theory: consecutive integers divisible by at least n prime numbers

Claim: There exist 15,251 successive positive integers $a_1, a_2\dots,a_{15251}$ such that each $a_i$ where ($1\le i\le 15251$) is divisible by at least 251 different prime numbers Is there a neat ...
0
votes
1answer
25 views

Prove that for a sequence of people sets $S_1,…,S_d$, $\Delta_i \not = 0$ for all people

We have $k$ people $p_1,...,p_k$, and $d$ people sets $S_1,...,S_d$, where the sizes of $S_1,...,S_d$ can vary between $1$ and $k$ (so each $S_1,...,S_d$ is a set of some people from ...
4
votes
1answer
81 views

Proof of $p_n<n^2$ by Elementary Means

Is there any proof of the inequality $p_n<n^2$ (for all sufficiently large $n$) by elementary means and without using Prime Number Theorem? I searched in google but in vain. The results that I ...
4
votes
0answers
32 views

Arithmetic Functions: Evaluate $ \sigma(210)$ and $d(63)$

Evaluate $ \sigma(210)$ and $d(63)$ I'm not sure if I got this correct, so here is my attempt. By Theorem 6.3, suppose we have $n=p_1^{\alpha 1}...p_s^{\alpha s}$, then $d(n) =(\alpha_1 ...
0
votes
0answers
27 views

A Contradiction of Riemann Zeta Residues

We can show (1+2+3...+n)^2 = 1^3 + 2^3 + ... +n^3, which holds for any finite n, shouldn't this imply Z(-1)^2 = Z(-3)? However, this does not hold if we look at the residues of the zeta function ...
0
votes
1answer
18 views

Finding permutation $a$ given $b$ and conjugate $a^b$

Normally we define a conjugate relationship as $$a^b = b~a~b^{-1}$$ But I don't know how to find $a$ given that we know $b$ and $a^b$.
3
votes
1answer
46 views

Eulers totient function divided by $n$, counting numbers in the set [1,m] that are coprime to n

If we divide Euler's totient function $\omega(n)$ by $n$, we obtain a fraction. If we multiply this fraction by any natural number $m$ which gives us another natural number $p$, is it true that $p$ is ...
1
vote
0answers
45 views

Show that $-1$ is a square $\mod n$, if $n\equiv 1\mod 4$?

I am trying to prove that $-1$ is a square modulo $n$ if, and only if $n\equiv 1\mod 4$. One direction i think i have done... So, we have that $n\equiv 1\mod 4$, from this follows that $n$ must be ...
0
votes
1answer
22 views

Proof by induction with two variables

Giving proof by induction is normally very straight forward: $n+1$ and such. But how do you deal with two variables $m$ and $n$? Given this problem, how do I ensure that I'm proving for $n+1$ and ...
0
votes
2answers
20 views

How to find sum of powers from 1 to r

Let say I have two numbers n power r. How can we find sums of all powers. For example if n = 3 and r 3 then we can calculate manually like this ...
-1
votes
1answer
35 views

Arithemetic series addition

Lets say I have M= 1+2+3+4+5+6+7.... (to infinity) and I have another sequence,N= 6+14+22+30..... (to infinity) is it possible to say that N = 4M +2 ? Or is there another way that I can write ...
0
votes
0answers
15 views

galois group of a biquadratic involving primes.

Let $f(x)=x^4-px^2+q \in \mathbb Q[x]$ be a polynomial with $p,q$ be distinct primes. Prove that $f$ it's irreducible over $\mathbb Q$. Prove that it's Galois group is the dihedral. I proved the ...
0
votes
1answer
27 views

Partial sums of powers of the divisor function

It is easy to establish that $$\sum_{n\le x}\tau(n) \sim n\log n$$ How would one find good bounds on $$\sum_{n\le x} \tau(n)^k $$ for some $k > 0$
1
vote
2answers
16 views

If p is an odd prme and (t,p) = 1, then t^2 is not a primitive root (modp).

If p is an odd prime and (t,p) = 1, then t^2 is not a primitive root (modp). proof: If g is a primitive root (modp) and if t is an integer such that (t,p) = 1, then there exist an integer k such ...
0
votes
0answers
18 views

Is it a case of a mixed-integer problem?

I have been faced with a problem for quiet some time and don't know how to go further. The problem is as follows and would appreciate any help on formatting this problem in terms of mixed-integer ...
1
vote
0answers
31 views

Question about series and how the pattern idea works

Two Questions: When you are given: $1, 2, 3, .... , n$ How do you know that in the $...$ that it continues the $x_{n-1} + 1$ pattern? Is it the definition of series? Secondly: Do partial sums ...
-1
votes
0answers
50 views

Is the polynomial $X^{32} + 1$ irreducible? [closed]

I think this question is interesting for Fermat number. Is this polynomial irreductible in $Z[X]$ ?
2
votes
1answer
50 views

Fermat solved $x^2+2=y^3$ by infinite descent?

In a letter to Christiaan Huygens entitled "on problems in the theory of numbers: a letter to Christiaan Huygens", Fermat claism that he solved the diophantine $x^2+2=y^3$ using infinite descent. Here ...
0
votes
1answer
44 views

Is it possible to find $n-1$ consecutive composite integers

Given an integer $n\geq 2$ ,can we always find an integer $m$ such that each of the $n-1$ consecutive integers $m+2,m+3,.....,m+n$ are composite?
0
votes
0answers
30 views

Count of 1's in the binary notation of a number

Let $f(x)$ be the count of 1's in the binary notation of number $x$ . Find minimal $g(x)$ for what $f(3^n-1)\le g(n)$ for all $n\ge1$ . I think that $g(x)=x$ but I can't prove it . For $n=1,\ldots,10$ ...
2
votes
0answers
54 views

Mellin transform on $\mathbb{Z}[\omega]$

Let $\omega=\frac{-1+i\sqrt{3}}{2}$ be a complex cube root of unity. The Eisenstein integers $\mathbb{Z}[\omega]$ (a unique factorization domain) are of the forms $a+b\omega$ where $a$ and $b$ are ...
3
votes
1answer
39 views

Calculating zeta functions over a field

I am learning about zeta functions and have been trying the following example: Calculate the zata function of $x_0x_1-x_2x_3$ over $\mathbb{F}_p$. Does there exist an easy formula for calculating ...
4
votes
1answer
24 views

Inertia Degree in Cyclotomic Extensions

Let $\zeta$ be a primitive $l$th root of unity, where $l$ is prime. If $p$ is another prime number, let $f$ be the order of $p$ in $U(\mathbb{Z}/l \mathbb{Z})$. Then in $\mathbb{Z}[\zeta]$, $p$ ...
1
vote
2answers
31 views

The set $\mathbb{Z}$ is totally ordered

Having the following definition of the $\leq$-Relation in $\mathbb{Z}$: For $a, b\in \mathbb{Z}$ we define $$ a \leq b : \iff b-a \in \mathbb{N} $$ Show that $(\mathbb{Z}, \leq)$ is totally ...
8
votes
2answers
179 views

On the difference between consecutive primes

Let $(p_n)$ be the sequence of prime numbers and $g_n = p_{n+1} - p_n$ Question: Is it known that $g_n \le n$? Remark: it's known that $g_n < p_n^{\theta}$ with $\theta = 0.525$ for $n$ ...
0
votes
2answers
69 views

Set of numbers which can not be represent as $a_1^n+a_2^n+…a_n^n$

Consider the set of natural numbers which can not be represented as $a_1^n+a_2^n+....a_n^n$ where $a_1,...,a_n$ are non-negative integers , n - given natural number . Is this set infinite or not?
0
votes
2answers
48 views

Beautiful little number theory prob

Solving (a,b) + [a,b] = ab for natural a,b. How many possible a's are there. I only know that (a,b)[a,b] = ab. Tried factoring out (a,b), but can't derive from it.
0
votes
1answer
18 views

Does there exist a Unit Matrix for a m x n matrix?

By definition, a Unit/Identity matrix (I) is a matrix such that, I A = A I = A If the matrix A is of dimension m x n, then unit matrix in IA must be of dimention m x m, while in A I should be of ...
3
votes
0answers
50 views

Proving that table totals can always be preserved with ceiling and floor

$\begin{array}{|c|c|c|c|} \hline 11.998& 9.083 & 2.919 & &24 \\ \hline 12.983&10.872&3.145&&27\\ \hline 1.019&2.045&0.936&&4\\ \hline & & ...
5
votes
4answers
99 views

how do I find the continued fraction of root n ?? [duplicate]

I saw a site where they explained it.but it required calculator.I want to do it without calculator. Can anyone please help me?
3
votes
0answers
40 views

Lucas' Theorem for $p$-adic integers?

Does Lucas' Theorem hold for $p$-adic integers? More specifically, does it specifically hold for the case that, given a $p$-adic integer: $$x = x_0 + x_1p + x_2p^2 + \cdots = \sum_{i=0}^\infty ...
1
vote
1answer
32 views

Something similar to Euler's theorem

If $p$, $q$ are not equal primes. $n=pq$, $\varphi(n) = (p − 1)(q − 1)$, $d = \gcd(p − 1, q − 1)$. Is it true that for any $a$ such that $\gcd(a, n) = 1$ holds $a^{\frac{\varphi(n)}{d}} \equiv 1 ...
0
votes
1answer
12 views

Show that $\frac{1}{e^\gamma \text{log }x + O(1)} = \frac{1}{e^\gamma\text{log }x} + O\left(\frac{1}{(\text{log }x)^2}\right)$

Show that $\frac{1}{e^\gamma \text{log }x + O(1)} = \frac{1}{e^\gamma\text{log }x} + O\left(\frac{1}{(\text{log }x)^2}\right)$ I'm using one of Merten's estimates in a proof, the one that states ...
1
vote
1answer
27 views

Why is it impossible that $\frac{\phi(n^*)}{n^*} < \frac{\phi(n)}{n}$ when $n^* < n$

Why is it impossible that $\frac{\phi(n^*)}{n^*} < \frac{\phi(n)}{n}$ when $n^* < n$ and $n$ has $k$ prime factors, and $n^*$ is the product of the first $k$ prime factors? I understand that ...
-1
votes
0answers
13 views

Square classes of transcendental extension of p-adic fields.

Let $k = \mathbb{Q}_p(t)$ with $p \neq 2$. What is known about the order of $k^*/k^{*2}$ ? In the case $k = \mathbb{Q}_p$ we have that $k^*/k^{*2}$ is isomorphic to the Klein four group. So i guess ...
-2
votes
0answers
30 views

The diophantine equation $A^2+B^2=C^2$ for integer-valued polynomials [on hold]

How can I find the solutions to this diophantine equation in $\Bbb{Z}[X]$: $$A^2+B^2=C^2 \, ?$$ Here $A$, $B$, $C$ are polynomials.
0
votes
1answer
19 views

Equivalence for binary quadratic forms with positive square discriminant

I recently encountered an interesting proposition without proof: If $f(x,y)$ is a quadratic form whose discriminant is a non-zero perfect square, then $f(x,y)$ is equivalent to a form $a*x^{2} + ...
1
vote
2answers
23 views

Stuck with modular arithmetic problem using multiplication property

I have the following problem: Given $k\geq 1$, find $h$ such that $$2^h \frac{4^k-1}{3}-1 \equiv 0 ~(\text{mod}~3).$$ This is my attempt using the invariance of multiplication: $$2^h ...
0
votes
1answer
46 views

Trying to show that $\phi(n) > c_1 \frac{n}{\text{log log }n}$ for some constant $c_1 > 0$

Trying to show that $\phi(n) > c_1 \frac{n}{\text{log log }n}$ for some constant $c_1 > 0$ where $\phi(n)$ is the euler phi function. I was wondering if I could use something like ...
1
vote
5answers
40 views

Intuition to why average of the square of a positive integer and the integer itself is the sum of all numbers from 1 to the integer?

The sum of all numbers from 1 to n, i.e. $\sum_{i=1}^n i = \frac{n(n+1)}{2} = \frac{n^2 + n}{2}$ This happens to be show that the average of a number and its square equals the sum of all numbers ...
1
vote
1answer
46 views

Show that if x,y,z are not divisible by 53, then $x^{26}+4y^{26} \neq\ z^{26}$

Show that if x,y,z are not divisible by 53, then $x^{26}+4y^{26} \neq\ z^{26}$ I've got that $x,y,z$ to the 52nd power are congruent to 1 modulo 53 from Fermat's. How is it continued? Help would be ...
0
votes
1answer
21 views

Find all $(h,k)$ such that $2^h \equiv 1 ~(\text{mod}~ 3^k) $

I'm facing with the following problem: Find all $(h,k)$ such that $$2^h \equiv 1 ~(\text{mod}~ 3^k) ~~~~~~~~(1)$$ and $$2^h \geq 3^k+1 ~~~~~~~~(2).$$ I'm just able to prove that the $(1)$ holds ...
-2
votes
0answers
27 views

Ways of representing the product of N numbers as sum of two squares [on hold]

Given N numbers, we need to tell the number of ways of representing the product of these N numbers as sum of two squares. Example : Let $N=3$ and numbers be $[2,1,2]$ then as $2*1*2=4$ There are 4 ...
0
votes
1answer
52 views

Search for very large prime (greater than $2^{57885161} − 1$) between Crystal Numbers

Denote $p[i]$ as the $i$th prime. In my opinion, the following is true: Prime Gap Axiom There are always distinct prime factors for $\{p[i],p[i]+1,p[i]+2, \dots , p[i+1]\}$. Question 1 How to ...
2
votes
1answer
34 views

if this divisors such $d_{1}+d_{2}+\cdots+d_{k-1}=n-1$,then there exsit $m$ such $n=2^m$

Interesting Question: let $n\ge 2$ be a positive integer,with divisors $$1=d_{1}<d_{2}<\cdots<d_{k-1}<d_{k}=n$$ and such $$d_{1}+d_{2}+\cdots+d_{k-1}=n-1$$ show that:there ...
2
votes
1answer
32 views

Definition of field of fractions of $p$-adic integers

I am given this definition of the field of fractions of the p-adic integers: $$Q_p=\left\{ \frac{r}{s} \mid r, s \in Z_p, s \neq 0\right\}$$ How can I show that: $Q_p$ consists of the sums of the ...
-1
votes
1answer
57 views

how many people are at the party

At a party, each person shakes hands with 5 other people. There are a total of 60 handshakes. How many people are at the party? i am lost because of the 60 hand shake that is mentioned.