Questions on more advanced topics of number theory, such as quadratic residues, primitive roots, prime numbers, non-linear Diophantine equations, etc. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

learn more… | top users | synonyms (1)

1
vote
1answer
68 views

Does this function have a “name”, somewhat linked to Euler totient

If $\varphi$ denotes the Euler totient and $n=p_1^{k_1}\cdots p_r^{k_r}$ is the prime factorization of $n>1$ we have $ \varphi(n)= \varphi(p_1^{k_1}) \varphi(p_2^{k_2}) \cdots\varphi(p_r^{k_r})= ...
1
vote
4answers
74 views

How to prove this property of congruences?

Prove that for each $n \in \mathbb{N}, s \in \mathbb{N}$ the following is true (i) $n \equiv Q_s(n) \left(\bmod\ 10^s - 1\right)$ (ii) $n \equiv Q'_s(n)\left(\bmod\ 10^s + 1\right)$ where ...
1
vote
1answer
130 views

Question on Gauss sums

For characters, $\chi$ and $\rho$, if $k\in \mathbb{F_{p}}$ with $k\neq0$ and $\chi^{2}\neq \epsilon$, then suppose $\sum_{t}\chi{(t(k-t))}=\chi{(k^{2}/2^2)}J(\chi,\rho)$. How can I show that ...
1
vote
1answer
72 views

Are these subgroups conjugate?

Define the groups $$\Gamma_0^0(N,M) = \left.\left\{ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \in SL_2(\mathbb{Z}) \;\right|\; b = 0 \bmod N, \; c = 0 \bmod M. \right\}$$ and ...
1
vote
1answer
421 views

Relationship between Kronecker's Approximation Thm and Weyl's Equidistribution Thm?

According to Prof. Wikipedia, the Equidistribution Theorem was proved by Weyl in 1910 and independently by two others around the same time. The theorem states that for $\alpha$ irrational, the ...
1
vote
1answer
89 views

Decreasing function made up of cubes, squares and floor function

Let $t$ and $r$ be two integers with $r\geq 1, t\geq \frac{r}{2}$. Put $$ f(r,t)=\lfloor 2(t^2+r)^{\frac{3}{2}}-(2t^3+3rt) \rfloor $$ (here $\lfloor x \rfloor$ denotes the floor of $x$, i.e. the ...
1
vote
1answer
886 views

Lucas Theorem for combinatorics?

Can anyone give me an example of Lucas Theorem and how it works? What about for composite modulus?
1
vote
1answer
85 views

Proof $\left|N\right|=\left|M\right|$ with $M=(n_1,…n_s) \mid n_i$ and $N=(n_1,…,{n_s+1}) \mid n_i$

I have to solve the following and I don't know where to start: Let $w \in \mathbb{N}_0$, where $\mathbb{N}_0 = \mathbb{N} \cup \{0\}$. Furthermore, let $M=\{ (n_1,...,n_s) \mid n_i \in \mathbb{N}_0, ...
1
vote
1answer
71 views

How to show this estimate

$$\int_2^x\frac{\pi(t)}{t^2}dt=\sum_{p\leq x}\frac{1}{p}+o(1)\sim\log\log x.$$ I guess Abel's partial summation is needed, but I fail to use it.
1
vote
1answer
125 views

Quadratic form over the dyadic numbers

I would like to know whether $q=\langle 3,3,11\rangle$ (a diagonal ternary form) represents $2$ over $\mathbb{Q}_2$ (i.e. whether there exist $x,y,z\in\mathbb{Q}_2^\times$ such that $q(x,y,z)=2$). I ...
1
vote
1answer
211 views

A Rough Estimation for the number of square free integers

Show by a sieve argument that the number of square free integers not exceeding $x$ is less than $$x\prod_p\left(1-\frac{1}{p^2}\right)+o(x),$$where the product extends over all primes. I happened ...
1
vote
1answer
84 views

$\mathbb{Q}(t_1,…,t_n) \cap \overline{\mathbb{Q}}$

Let $\overline{\mathbb{Q}}$ the algebraic closure of $\mathbb{Q}$, and $K$ a field extension of $\mathbb{Q}$ (not necessarily algebraic) such that $[K:\mathbb{Q}]= \infty$. Let $t_1,...,t_n \in K$, ...
1
vote
1answer
210 views

A Generalization of Cantor's counting theory

This question may be silly to experts, but I am waiting for a response sir. My question is " Is there any existence of generalized Cantor's counting principle ( i.e the theory that decide ...
1
vote
2answers
238 views

Problems about “necklace”

Here necklace has its common combinatorial sense. If the type of a necklace is the number of things in the necklace, 1100:1100, 0110, 0011, 1001--type 4 then how many necklaces are there of type n, ...
1
vote
1answer
99 views

Nice description of $(1+2\mathbb{Z}_2)^{2^k}$?

For $p\neq 2$ it's easy to prove through the log/exp-correspondence that $$(1+p\mathbb{Z}_p)^{p^k}=1+p^{k+1}\mathbb{Z}_p.$$ This gives an easy way to compute the groups ...
1
vote
1answer
254 views

Fencing the Group size,and its implication to Finiteness of Tate-Shafarevich Group

This question is an interesting one,not like my previous one. Can we judge the size of a Quotient Group by seeing the size of its constituents ? To add something ,Suppose consider a group ...
1
vote
1answer
137 views

How many $n$'s can make $4m^2-n^2$ a perfect square? And, triple of a perfect square?

As the title reads. Given an integer $m\ge1$, how to calculate the number of integer $n$'s ($1\le n\le 2m$) such that $4m^2-n^2$ is a perfect square? Thank you~ Update: Further, how many pairs ...
1
vote
1answer
114 views

Something basic in “l-adic properties of the partition function” paper

I am trying to understand the basic result in this paper: http://www.aimath.org/news/partition/folsom-kent-ono.pdf My problem is with the example at the end of page 2. I understand it's supposed to ...
1
vote
2answers
124 views

Two succeeding integers in $\left(\mathbb{Z}/n\mathbb{Z}\right)^{*}$ for an odd n, and the Jacobi symbol of the latter one

Given an odd integer $n$, I want to find out if there exists two succeeding integers, $1\leq m-1<m\leq n-1$ s.t both are invertible (i.e $m,m-1\in \left(\mathbb{Z}/n\mathbb{Z}\right)^{*}$) and also ...
1
vote
1answer
217 views

Congruence subgroup of $SL_2(\mathbb{Z})$ definition

Congruence subgroups of $SL_2(\mathbb{Z})$ usually seem to be defined as a subgroup that contains $\Gamma(N) = \left\{\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \mod N \right\}$ for some ...
1
vote
1answer
214 views

On the equation $3a^2-4b^3=7^c$

How does one find all integer solutions to the equation $3a^2-4b^3=7^c$?
1
vote
1answer
220 views

Modular forms question

Can someone enlighten me with the question in the next page: http://www.physicsforums.com/showthread.php?p=3208664#post3208664 I am asked to find all the modular forms with weight $k$ which don't ...
1
vote
1answer
344 views

Understanding a counterexample to Hasse principle

I'd like to understand a step in a counterexample of Reichardt and Lind to the Hasse principle. The example is given by the equation $2y^2=x^4-17z^4$ (1). (1) has no rational solutions ($\neq ...
1
vote
1answer
218 views

contour integration $\zeta(s)\zeta(2s)$ and $x^s/s^(k+1)ds$

I am trying to do contour integration on $\int_c \zeta(s)\zeta(2s) \frac{x^s}{s} ds$ and $\int_c \frac{x^s}{s^ks}ds$ where c is the line segment joining c-iT c+iT I understand the basic theory ...
1
vote
2answers
1k views

What is an efficient algorithm to compute modular exponentiation of stacked exponents?

Given $a^{b^c}\mod p = x$, where $a,b,c$ are real positive integers and $p$ is a prime, what is the most efficient algorithm to compute $x$ (ideally in polynomial time)?
1
vote
1answer
200 views

Showing that $|\sqrt{3} - m/n| \geq 1/(5n^2)$

Can you help me to prove this inequality \begin{aligned} |\sqrt{3} - m/n| \geq 1/(5n^2) \end{aligned} where m and n are integers. Hint:$sqrt(3)$ is irrational.
1
vote
1answer
191 views

Multiplicative order of elements in an imaginary quadratic field

Let $K$ be an imaginary quadratic field and $U$ denote the unit group in the ring of integers in $K$. Are there $\alpha \in K-U$ with finite multiplicative order? That is, is there $n \in N$ such ...
1
vote
1answer
356 views

Pigeonhole principle question

Suppose a graph with 12 vertices is colored with exactly 5 colors. By the pigeonhole principle, each color appears on at least two vertices. True or false? The correct answer is false, but I assumed ...
1
vote
1answer
139 views

Parity of $k = d d^{\prime} > 1$ vs $\text{gcd}(d+1,d^{\prime} +1)$ for distinct divisors $d$ and $d^{\prime}$

I've recently come upon the following (seemingly) simple observation: Claim: A positive integer $k = d d^{\prime} > 1$ has the opposite parity of $\text{gcd}(d+1,d^{\prime}+1)$ for any pair of ...
1
vote
2answers
336 views

proving $\sum\limits_{k=1}^{n} \Bigl\lfloor{\frac{k}{a}\Bigr\rfloor} =\Bigl\lfloor{\frac{(2n+b)^{2}}{8a}\Bigr\rfloor} $

There was a problem in Apostol's book namely, to prove that: $$\sum\limits_{k=1}^{n} \Biggl\lfloor{\frac{k}{2}\Biggr\rfloor} = \Biggl\lfloor{\frac{n^{2}}{4}\Biggr\rfloor}$$ which i could solve. The ...
1
vote
2answers
461 views

Radius of Convergence of a given Power series

I came across this question. Let $d(n)$ denote the number of divisors of $n$. Let $$\nu(z) = \sum\limits_{n=1}^{\infty} d(n) z^{n}$$ Whats the radius of convergence of this power series. We also have ...
1
vote
2answers
404 views

Legendre functions in number theory

I have heard that Legendre functions are important in number theory. Can any one tell me how? The Legendre function of the first kind $P_s$ is defined by \begin{eqnarray*}P_s(x) =& ...
1
vote
1answer
22 views

Largest Number that cannot be expressed as 6nm +- n +- m

I'm looking to find out if there is a largest integer that cannot be written as $6nm \pm n \pm m$ for $n,m$ elements of the natural numbers. For example, there are no values of $n,$m for which $6nm ...
1
vote
1answer
26 views

Sum of digits of polynomial smaller than of factorial

I'm trying to prove this : Let $f \in Z[X]$ then for sufficiently large $n$ we have $$s(f(n))<s(n!)$$ where $s$ is the sum of digits function. What I have so far : I thought this must be true ...
1
vote
1answer
32 views

How do I get rid of the coefficient in this congruence?

$$ax^2 = b \bmod m$$ I am trying to get rid of the $a$ so I can apply Tonelli-Shanks to the result to solve for $x$. But since $a$ and $m$ are not always coprime, I cannot always multiply both sides ...
1
vote
2answers
127 views

Primality of $2^{255}-19$

I need a test for primality that I apply to $2^{255}-19$ (which is claimed to be prime) and certify to be correct with the ACL2 theorem prover. This means that I must be able to code the test in ...
1
vote
1answer
25 views

G finite group with the following characteristics

G is closed finite group with an associative operator with the following parametres/characterstics: For each $x,y\in G$ if $ax = ay$ then $x = y$ for each $a\in G$ For each $w,z\in G$ if $wa = za$ ...
1
vote
1answer
39 views

Is this a correct proof that $\tau(n)$ is eventually smaller than any $n^{\delta}$, $\delta>0$?

Is this a correct proof that $\tau(n)$ is eventually smaller than any $n^{\delta}$, $\delta>0$? I'm not even sure about the statement, let alone the proof. Let's first proof this result: $\tau(n) ...
1
vote
2answers
78 views

Explain the proof of irrationality of $\sqrt{2}$

How does this proof show the irrationality of $\sqrt{2}$ ? I am new to proofs and don't really understand the logic used here.
1
vote
2answers
50 views

Reflection formula for Hurwitz Zeta function?

In doing some calculus with Mathematica today, I found that $$\zeta\left(3,\frac{1}{4}\right) - \zeta\left(3,\frac{3}{4}\right) = 2\pi^3$$ by numerically evaluating both sides. Here, $\zeta(x,y)$ ...
1
vote
1answer
49 views

How one can solves an equation of the form: $ap_{n}+bn=c$

My question is: How can one solve an equation of the form: $$ap_{n}+bn=c$$ where $p_{n}$ is the $n^{th}$ prime number, $a,b$ and $c$ are integers.
1
vote
1answer
73 views

Number of zeros at the end of $k!$

For how many positive integer $k$ does the ordinary decimal representation of the integer $k\text { ! }$ end in exactly $99$ zeros ? By inspection I found that $400\text{ !}$ end in exactly $99$ ...
1
vote
1answer
32 views

Fermat primality test and Fermat pseudoprime

What is the difference between Fermat primality test and Fermat pseudoprime?Can anyone explain me how we use them ?
1
vote
1answer
43 views

Congruence using extended GCD

$$\eqalign{ x &\equiv 5 \mod 15\cr x &\equiv 8 \mod 21\cr}$$ The extended Euclidean algorithm gives $x≡50 \bmod 105$. I understand now that if we combine the two it implies ...
1
vote
2answers
49 views

Why is this congruence true?

$$\eqalign{ x &\equiv 5 \mod 15\cr x &\equiv 8 \mod 21\cr}$$ The extended Euclidean algorithm gives $x≡50 \bmod 105$. How/why? I am trying to understand how this is true when ...
1
vote
1answer
40 views

NumberTheory: Proof or disproof the following. Dividing and adding

Proof or disproof the following. Let $N \in \mathbb{N}$ be a natural number. If we divide the digits of $N$ with preserving the order and adding them together we will get a digit ( a number less ...
1
vote
1answer
22 views

Why the action of $\mathrm{Gal}(\overline{\mathbb Q}_p/\mathbb Q_p)$ on $\overline{\mathbb Q}_p$ restricts to $\overline{\mathbb Q}$?

Let $\overline{\mathbb Q}$ be the algebraic closure of $\mathbb Q$ in $\mathbb C$ and chose an algebraic closure $\overline{\mathbb Q}_p$ for $\mathbb Q_p$. The embedding $\mathbb Q \hookrightarrow ...
1
vote
2answers
63 views

How to check this number $\sqrt{47}$ is irrational [duplicate]

Prove that $\sqrt{47}$ is irrational number. I know that a rational number is written as $\frac{p}{q}$ where $p$ & $q$ are co-prime numbers. But I do not have any idea to prove it irrational ...
1
vote
2answers
40 views

If $p$ is a prime number and $p\equiv 1(mod 4)$, (show that) there exist integers $a$ and $b$ such that $a^{2}+b^{2}=p$.

I'm reading a book on number theory (Theory of Numbers, Niven), and yesterday I've stumbled upon a proof of the above lemma (Lemma 2.13; page 54-55). I've managed to wrap my mind around the proof from ...
1
vote
1answer
31 views

Why only congruence subgroups for modular forms?

When we define modular forms, why do we restrict ourselves to congrumence subgroups? Why not any subgroup of finite index? Or, even more generally why not any subgroup? Is it just a matter of ...