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)

2
votes
1answer
73 views

Counting squarefree numbers which have $k$ prime factors?

How to find an asymptotic formula for this function below? $$f(n)=\sum_{pq\leq n}1$$ where $p$ and $q$ are different prime numbers. I guess we can write $$f(n)=\sum_{p\leq \sqrt{n}}\pi (\frac{n}{p})...
2
votes
1answer
106 views

Strange Algebraic Number

We call a number algebraic if and only if it is the solution of a polynomial with integer coefficients. A number (complex or real) is transcendental if and only if it is not algebraic. A while back ...
2
votes
1answer
54 views

On ramification index of a congruence subgroups at cusps

I am trying to solve this problem from Koblitz "Introduction to Elliptic Curves and modular forms" page 144, where $\Gamma=\mathrm{SL}_2(\mathbb{Z}),$ and $T=\left(% \begin{array}{cc} 1 & 1 \\ ...
2
votes
1answer
31 views

Relating a Character sum to a Gauss sum

Let $q$ be a prime power. Consider the mapping $f:(\mathbb{F}_q)^{\times} \to (\mathbb{F}_q)^{\times},$ where $x\mapsto x^2$. I was interested in sums of the form $$\sum_{t\in \mbox{Im}(f)} \psi_a(t)\...
2
votes
2answers
77 views

Calculate φ(36), where φ is the Euler Totient function. Use this to calculate 13788 (mod 36).

Hello I am wondering if any one can help me I am trying to figure out how to Calculate $φ(36)$, where $φ$ is the Euler Totient function. Use this to calculate $13788$ $(mod 36)$. I have an exam ...
2
votes
2answers
38 views

A diophantine related query

Supposing I give you a multivariate equation $$F\in\Bbb Z[x_1,\dots,x_n]$$ Following is undecidable: 'Is there an $(a_1,\dots,a_n)\in\Bbb N^n$ such that $F(a)=0$?' However is the following always ...
2
votes
3answers
71 views

Bezout's Identity proof and the Extended Euclidean Algorithm

I am trying to learn the logic behind the Extended Euclidean Algorithm and I am having a really difficult time understanding all the online tutorials and videos out there. To make it clear, though, I ...
2
votes
1answer
63 views

How to derive sequence from generating function?

If you are solving a problem and you encounter a generating function that you haven't seen before, is there a way to derive its underlying sequence representation? For example I came across $\frac{1}{...
2
votes
1answer
47 views

How many times do I loop Solovay--Strassen primality test

First, I am aware of this former thread: math.stackexchange Yet it doesn't answer my question. If I want to check if an integer $n$ is prime using the Solovay--Strassen test, how many times do I ...
2
votes
1answer
105 views

“The PNT obtained by statistical methods”

In a famous book "What is Mathematics" by Richard Courant, Herbert Robbins the authors presented not a rigorous proof, but "an argument that at least makes plausible the truth of Gauss's famous ...
2
votes
1answer
43 views

Properties of Landau symbols

I am just looking for some clarification of some of the properties of Landau symbols. I know and understand the following multiplicative properties: $f(x)O(1)=O(f(x))$ $O(f(x))O(1)=O(f(x))$ $O(f(x))...
2
votes
3answers
71 views

Find all non negative integers x,y,z so we get a whole square

Find all $x,y,z\in\mathbb{N_0}$ so that there exists a $k\in\mathbb{N}$ so that $$4^x+4^y+4^z=k^2$$. We can transform this problem to: Find all $a,b\in\mathbb{N_0}$ so that there exists a $t\in\...
2
votes
1answer
39 views

the way to calculate the number of element in $\mathbb Z^*_n$ have order 2?

I want to show that if $n=pq$ such that $p$ and $q$ are distinct odd primes the number of $\ (a,b)$ such that $a$ and $b \in \mathbb Z_n$ and $a\equiv a^{-1}\pmod n$ and $b(a+1)\equiv0\pmod n$ is $n+...
2
votes
1answer
47 views

Show that $r$ is a primitive root (mod $p^k$)

Let $p$ be an odd prime, and let $r$ be a primitive root (mod $p$) such that $r^{p-1} \neq 1$ (mod $p^2$). Show that $r$ is a primitive root (mod $p^k$) for all $k \geq 1$. So I start of by computing ...
2
votes
2answers
101 views

On $p^2 + nq^2 = z^2,\;p^2 - nq^2 = t^2$ and the “congruent number problem”

(Much revised for brevity.) An integer $n$ is a congruent number if there are rationals $a,b,c$ such that, $$a^2+b^2 = c^2\\ \tfrac{1}{2}ab = n$$ or, alternatively, the elliptic curve, $$x^3-n^2x = ...
2
votes
1answer
50 views

Generalizing the norm and trace of finite extensions over finite fields.

I'm currently reading through Ireland and Rosen's A Classical Introduction to Modern Number Theory, and I'm working on proving that a later definition of trace and norm of arbitrary finite algebraic ...
2
votes
2answers
109 views

Is there a well known nontrivial counterexample to this claim?

Suppose we have $A\subseteq\mathbb{N}$ with the property that if $B\subseteq\mathbb{N}$ and $B$ is finite, then $\exists a\in A\setminus\{ 1\}$, $\forall b\in B$, $\gcd(a,b)=1$. Are there any well ...
2
votes
1answer
43 views

Can the existence of infinitely many even perfect numbers be settled by a diagonal argument?

Say a (finite or not) sequence of strictly increasing positive integers $(u_{i})_{i\in I}$ is a 'Euclid sequence' if and only if the sum of reciprocals of all the $(u_i)$ equals $2$. Now suppose we ...
2
votes
1answer
33 views

Intersection of three period functions

Let $f(x)=\frac{1}{2}-|\frac{\sqrt{3}}{2}x-1/2|$ for $x\in [0,\frac{2}{\sqrt{3}}]$ and $f(x+\frac{2}{\sqrt{3}})=f(x)$ for all $x\in\mathbb{R}$. $g(x)=\frac{1}{2}-|\frac{1}{2}x-1/2|$ for $x\in [0,2]$ ...
2
votes
2answers
44 views

Short gcd proof

Suppose $a,b\in\mathbb{Z}$ that $a$ and $b$ are both positive and that $gcd(a,b)=d$. Prove that if $n\in\mathbb{Z}$ is positive, the $gcd(an,bn)=dn$. My attempt... $gcd(a,b)=d$ so $d|a$ and $d|b$. ...
2
votes
1answer
42 views

How to find the number of $n$ for which $n!$ is divisble by $a$ but not $b$?

The values of $a$ and $b$ are known . I need to find the number of $n$ for which $n!$ is divisible by $a$ and not by $b$. Suppose $a=2$ , $ b=3$ then the possible solution is $1$ only for $n=2$.
2
votes
1answer
46 views

valuation of a particular element in $\Bbb{Z}_p$

Consider $x \in \Bbb{Z}_p$. Then I want to find the valuation of $(1+p)^x-1$. I think that $val_p((1+p)^x-1)=1+val_p(x)$. Is this right? Actually I want to prove that $min\{val_p(1+p)^x-1, val_p(...
2
votes
1answer
69 views

Sum of arithmetico-geometric series

Could use help trying to find the following sum of series $$ \sum_{n=1}^N r^n\sqrt{a + nd} $$ I have no clue where to begin on this one. Ideally would like solution for all $ r $ but if it helps ...
2
votes
1answer
59 views

When are both $x$ and $ y$ rational in $ x^2 + y^2 = k$

Under what conditions for k such that the circle equation $x^2 + y^2 = k$ has rational solutions for both $x$ and $y$? For example, when $k = 4$, $\{x=2, y=0\}$ is a set of rational solutions. But ...
2
votes
1answer
37 views

Relation between a quadratic residue and it's order

In the context of the multiplicative group $(\mathbb{Z}/m\mathbb{Z})^\times$ of congruence classes modulo $m$ coprime with $m$, is there a theorem that states something about the order of a given ...
2
votes
1answer
49 views

polynomials and symmetric functions

Suppose I have a polynomial function $f\in \mathbb{Z}[x_1, \dotsc, x_k],$ such that whenever $r_1, \dotsc, r_k$ are roots of a monic polynomial of degree $k$ with integer coefficients, we have $f(r_1, ...
2
votes
1answer
22 views

How did Chebyshev prove this weaker form of Rosser's theorem?

I have come to know of an elementary proof, by Chebyshev, that there exists a real $\alpha<1$ such that $$ p_n > \alpha n \log n, $$ where $p_n$ is the $n$-th prime. As I am failing to find it ...
2
votes
1answer
34 views

Congruence relation I'm having trouble with

I have this specific congruence relation, and although solving it with a calculator is trivial, I'd like to know what strategy I can use to solve this by hand. The relation is $79^7 \equiv x \mod ...
2
votes
1answer
54 views

Construction of the pre-addition

We know that the multiplicative operator is construct by iterating the additive one, and the power operator is construct by iterating the multiplicative one. Which makes us wonder if we can ...
2
votes
2answers
40 views

Show that $\sum_{z=1, \, z|n}^n z^2 \mu(z/n) = n \phi(n) \prod_{p|n} \left( 1+\frac{1}{p} \right)$

Show that $$\sum_{z=1, \, z|n}^n z^2 \mu(z/n) = n \phi(n) \prod_{p|n} \left( 1+\frac{1}{p} \right).$$ I have no idea how to show this. I tried different things for few hours and now Im out of ideas ...
2
votes
1answer
57 views

What is the maximum number of prime numbers by which N can be divided?

MyApproach $$(a+1)(b+1)(c+1)\cdots=45$$ To see maximum number of prime numbers by which $N$ can be divided. $a,b,c$ are the powers of prime numbers. I took factors of $45$. I got $3^2 \cdot 5$. ...
2
votes
2answers
51 views

show that for any prime p: if $p|x^4 - x^2 + 1$, with $x \in \mathbb{Z}$ satisfies $p \equiv 1 \pmod{12}$?

show that for any prime p: if $p|x^4 - x^2 + 1$ satisfies $p \equiv 1 \pmod{12}$ I suppose that if $p$ divides this polynomial we can see that: $x^4 - x^2 + 1 = kp$ for some $k \in \mathbb{N}$. But ...
2
votes
1answer
41 views

Find the five smallest positive integer $W$

Find the five smallest positive integer $W$ of at least two digits with the properties: $W=\frac{(m)(m+1)}{2}$ for some integer $m$. Every digit of $W$ is the same. I was able to find two of the ...
2
votes
1answer
82 views

Mobius function vanishes over sum of totient numbers

Let k be a positive integer. I need to prove that the sum $$\sum_{n \in \mathbb{N} : \phi(n)=k} \mu(n)=0$$ where $\phi$ is the Euler Totient function and $\mu$ is the Mobius function. Here is what I ...
2
votes
1answer
48 views

The number of e-th power residues $\bmod m$

For each positive integer $m$ define $\Bbb{Z}_m = {0, 1, 2, \ldots , m − 1}$, the set of all residues modulo $m$, and define $$C(m,e) = \{ k ∈ \Bbb{Z}_m \mid 0 \ne k ≡ a^e \pmod m \text{ for some }a ...
2
votes
1answer
26 views

Suppose $a,b,c > 0$. Then there are finitely many integer $x,y$ with $a^x > cb^y$.

Here is the question: For this question, it says to find finitely many positive numbers pairs of x and y for to fulfill the inequality. My thought is when [A] bigger than 1 or b is smaller than 1, ...
2
votes
1answer
72 views

Divisibility by 41 and 5-digit number

How to prove that if a $5$-digit number is divisible by $41$,then all the numbers generated from it by cyclic shift are also divisible by $41$
2
votes
1answer
71 views

How many integers $m$ such that Euler Totient Function $\varphi(m)$ = a given integer?

(I didn't find any other posts related to this but I think this is a weird because my question seems like a very natural one.) Let $\varphi$ denote the Euler Totient Function. Given $m$ an even ...
2
votes
1answer
83 views

A positive integer a is self-invertible modulo p if and only if a ≡ ±1 (mod p).

What does it mean that "a positive integer is self-invertible modulo p"?
2
votes
3answers
25 views

Simple NT/Algebra Proof

Prove that if $(p-1)(q-1)\ge 1$, over positive reals greater than 1, then $p+q\ge 4$. In essence, it seems this is proving that if $p+q<pq$, then $p+q\ge 4$, but this doesn't necessarily help. ...
2
votes
1answer
50 views

Can a carmichael number have consecutive prime factors?

Is there a set $[p_1,p_2,...,p_n]$ of consecutive primes , such that $\prod_{j=1}^n p_j$ is a carmichael number ? For $3$ and $4$ prime factors, I checked upto $p_1\le 10^{10}$ without success. ...
2
votes
1answer
129 views

Binary Expansion of 2^n-1

Show that the positive integral multiples of $2^{n}-1$ when expressed in binary will have at least $n$ ones'. My work so far: Let $b(k)$ be the number of ones when k is expressed in binary and let $...
2
votes
1answer
84 views

N bits, flip exactly M bits at a time, what is minimum number of operations to get all 0's to all 1's?

Suppose I have n bits, all initially 0. I can flip any m of the bits (does not have to be contiguous) at a time (one operation). How many operations is required? When is it not possible? It seems ...
2
votes
1answer
26 views

Matrix of quadratic form (in Serre's general notion)?

I am currently reading Serre's book on arithmetic. In chapter four (page 27) he defines a general notion of the quadratic form as: Let $V$ be a module of a commutative ring $A$. A function $Q$ is ...
2
votes
1answer
70 views

Prime Divisors of $x^2 + 1$

If $x$ is even and $f(x)=x^2 + 1$ is indeed composite, are the prime divisors of $f(x)$ congruent to $1$ mod $4$?
2
votes
1answer
42 views

How to obtain the negative rational numbers

Is there any formula for generating negative rational numbers? Can Calkin–Wilf tree be used for negative numbers?
2
votes
1answer
104 views

Prime dividing binomial coefficient involving prime power

I was wondering if there was a straightforward proof of the following fact (which I can show is true for specific cases, but not generally): Let $n$ be composite, and let $p$ be a prime factor $n$. ...
2
votes
1answer
124 views

Can $\pi$ be rational in some base radix

I am from a physics background and my mathematics is not very good, so pardon my insolence with the question. Editing based on the comments : We know that $\pi$ in decimal (i.e. base 10) is ...
2
votes
1answer
54 views

Is it known whether the number of Proth-primes is infinite?

A prime number of the form $k\times 2^n+1$ with $n\ge 1\ ,\ k<2^n$ is called a Proth-prime. Is it known whether the number of Proth-primes is infinite ? It seems to be almost surely true that ...
2
votes
1answer
34 views

A finite number of smaller lengths, added together will exceed a longer length. whats this theorem called?

Like, you have a small string, if you put lots of these small strings end to end, you will exceed the length of any string after doing it a finite number of times. I think this was Galileo, euclidean,...