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
97 views

What is $[\frac{q}{p}]$ if $[\frac{-q}{p}]=1$?

What is $[\frac{q}{p}]$ if $[\frac{-q}{p}]=1$? There $[\frac{q}{p}]$ is Legendre symbol. In other words if $x^2 \equiv -q \pmod p$ is solvable, then is $x^2 \equiv q \pmod p$ solvable also? I get that ...
1
vote
1answer
74 views

Can anybody validate this WolframAlpha computation?

Can anybody validate this WolframAlpha computation? http://www.wolframalpha.com/input/?i=GCD%5BDivisorSigma%5B1%2Cx%5D%2C+DivisorSigma%5B1%2Cx%5E2%5D%5D Thank you!
1
vote
1answer
92 views

connect p-adic expansion and fundamental theorem of arithmetic?

On the way to explain a $p$-adic expansion, we consider, when dealing with natural numbers, if we take $p$ to be a fixed prime number, then any positive integer expansion in the form can be written as ...
1
vote
1answer
114 views

definition of divisor functions

I have a question about the definition of divisor functions when I was reading primes in tuples by Goldston, Pintz, and Yıldırım: Let $\omega(q)$ denote the number of prime factors of a squarefree ...
1
vote
1answer
174 views

What is the difference between multiplicative group of integers modulo n and a Galois Field

What is the difference between multiplicative group of integers modulo n and a Galois Field? Is $\mathbb{Z}^*_p$ with p prime the same as $GF(p)$? Or is it the same as $\mathbb{Z}/n\mathbb{Z}$? ...
1
vote
2answers
49 views

Need help understanding proof to their being a prime gap $G(p_k, p_{k+1})$ with $p_k \leq n$ and $p_{k+1} - p_k > \frac{1}{2}\ln(n)$

Let $p_k ( k \geq 1)$ be an enumeration of all the positive primes with $p_1 = 2$ and $p_k < p_{k+1}$ for all $k \geq 1$. Prove that if $n$ is sufficiently large, then there is a prime gap ...
1
vote
1answer
53 views

Checking if a solution exists across two inequalities

If I have $ay < x < by$ $cx < y < dx$ With $a,b,c,d$ as known (they are real-valued, can be positive or negative or 0) and $x,y$ unknown, is there a methodical way to see if a solution ...
1
vote
1answer
50 views

Elements and their properties in a finite field

I need help proving the following. If $\alpha \in (\mathbb{Z}/p\mathbb{Z})[x]/\langle f\rangle$ for some irreducible $f\in (\mathbb{Z}/p\mathbb{Z})[x]$ of degree $n$, then both ...
1
vote
1answer
105 views

probability of divisibility

Let S be the sum of k randomly selected integers between 1 and n. What is the probability of S being divisible q? Can this be expressed in a closed form? This is the generalization of one of the ...
1
vote
1answer
129 views

A Diophantine equation and decimal digits

Solutions of the Diophantine equation $a10^n+(a+1) = (2^{m+1}-1)*2^{m+1}$ are 12=3*4, 56=7*8, 67100672=8191*8192. Are there more solutions/examples like that or a generalization of the ...
1
vote
3answers
144 views

Primitive Roots

Given $p$, $q$ both primes such that $q = 2p + 1$, I need to prove that $-4$ is a primitive root mod $q$. So far haven't found a direction that could lead me to the solution. Any suggestion or short ...
1
vote
2answers
79 views

Binary Vector Communication

Alice holds an $n$ x $n$ binary matrix $A$, and Bob holds an $n$ x $n$ binary matrix $B$. They want to check whether $A = B$, but they do not want to communicate too much. Here is what they do: Alice ...
1
vote
1answer
48 views

What type of function is this close to?

Does anyone recognize this type of function, or is this similar to another function? I can see that it is discrete and that it has a point, (9, 30), where the function reflects and later repeats ...
1
vote
1answer
87 views

Divisibility problem.

In line written squares of natural numbers from 1 to 2012. How many of these numbers have a remainder when divided by 17, which is divisible by 3?
1
vote
2answers
296 views

Show that r is a primitive root?

Show that if $r$ is a primitive root modulo the positive integer $m$, then $ {\overline r }$ is also a primitive root modulo m if $ {\overline r }$ is an inverse of $r$ modulo $m$. My TA did not go ...
1
vote
1answer
113 views

Finding quadratic residues in a finite field by using a primitive element

Let $1+2x$ be a primitive element of the field $\mathbb F_9$ obtained via the irreducible polynomial $$x^2 + 1$$ over the base field $\mathbb F_3$. i) Make a list of the elements of $\mathbb F_9$ ...
1
vote
1answer
89 views

Prove that $\frac{m+n+2}{2(m+1)}{n\choose m}2^{(n-m)/2}$ is an integer

Let $m,n$ be positive integers, both odd or both even, with $n\ge m$. I think the following number $$\frac{m+n+2}{2(m+1)}{n\choose m}2^{(n-m)/2}$$ is always an integer, but I have trouble proving it.
1
vote
2answers
190 views

Number theory proof by counter example

Give an example of two cycles of lengths $r$ and $s$ respectively whose product does not have order $lcm(r,s)$
1
vote
1answer
79 views

Rational and irrational fractions over finite fileds [duplicate]

I've been told that over the field $\mathbb{F}_7$ the square root of $2$ is actually $3$. How come? Why does it happen?
1
vote
1answer
71 views

Iwaniec Kowalski Notation

On page 532 of the book analytic number theory by Iwaniec and Kowalski, the following notation is used: $C^{~\infty}$ and $\tau(n,\chi)$. Could anyone tell me what these represent? (the former is ...
1
vote
1answer
31 views

Groups $G$ of order $8$ so that $U(\mathbb{Z}/n\mathbb{Z})\cong G$ for some $n$.

I cant solve this exercise. Find all groups $G$ of order $8$ so that $U(\mathbb{Z}/n\mathbb{Z})\cong G$ for some $n$. I need a little help here. thanks!!!
1
vote
1answer
126 views

Groups of units: Find an explicit isomorphism $U_{35}$, $U_{39}$

I need help in the following exercise: Find an explicit isomorphism between $U(\mathbb{Z}/35\mathbb{Z})$ and $U(\mathbb{Z}/39\mathbb{Z})$. Thanks!
1
vote
1answer
44 views

$H_1, H_2$ groups. $|H_1 |= n_1, |H_2| = n_2$. Prove $|H_1 \times H_2| = n$ where $n = \mathrm{lcm}(n_1,n_2)$

Let $H_1$ and $H_2$ be groups. Prove that if $a_1 \in H_1$ has order $n_1$ and $a_2 \in H_2$ has order $n_2$, then the order of $(a_1, a_2)$ in $H_1 \times H_2$ is $n$, where $n = \mathrm{lcm}(n_1, ...
1
vote
1answer
37 views

Find values in formula $x * z_1 = y * z_2$

I'm working on a number generator for this little formula $x * z_1 = y * z_2$ The numbers are within this ranges: $x \in \{1, ..., 10\}$ $y \in \{1, ..., 10\}$ $z_1 \in \{2, ..., 100\}$ $z_2 \in ...
1
vote
1answer
93 views

3 complex-variable equation

Moderator Note: This is a current contest question on Brilliant.org. $x,y,z$ are complex numbers satisfying $$ \begin{align} x+y+z & =1\\ x^2+y^2+z^2 & =2\\ x^3+y^3+z^3 & =3 ...
1
vote
1answer
96 views

Dirichlets theorem on primes

I want to use Dirichlets theorem on primes for my diploma thesis. I want to use following form Let $a,b\in\mathbb{N}$, such that $\gcd(a,b)=1$. Then the set $\{a\cdot n+b| n\in\mathbb{N}\}$ contains ...
1
vote
1answer
36 views

Numerical upper bound of $o(1)$

What can be a numerical upper bound for the $x$ in the following formula ($n \ge 1$): $$x < ((1 + o(1))n\log n$$ I mean to replace $o(1)$ with some number or constant. Is it possible?
1
vote
4answers
167 views

Number Theory Question on the floor function

I'm trying to understand properties of the greatest integer function and I am struggling to find the value of $\lfloor x+y \rfloor$ where $x \in \mathbb{R}$, $y \in \mathbb{Z}$, and prove that it is ...
1
vote
1answer
67 views

Smallest $x$ that allows for division by $y$

Assume we know $y$ which is prime of form $6k+1$ (may not be relevant). I want a simplified way to find the smallest positive $x$ where $y$ divides $x^2-x+1$. Is there a better way than just testing ...
1
vote
1answer
57 views

Showing that if $p = k2^n+1$ with $k$ odd, then the Jacobi symbol $(\frac{k}{p})$ equals $1$

I am observing if $p = k2^n+1$ (a Proth number), $k$ is odd, there is always an integer $x$, such that $k = x^2 \bmod p$, i.e. the Jacobi symbol $(\frac{k}{p})$ is always $1$. Can someone give a ...
1
vote
2answers
377 views

Using Chinese Remainder Theorem for two equations with non-coprime moduli

I have \begin{align} x & \equiv a\mod m \\ x & \equiv b \mod n \end{align} Normally I would solve for $x$ by doing $(an\cdot \operatorname{inverse}(n,m) + bm\cdot ...
1
vote
1answer
387 views

Let $N$ = $11^2 \times 13^4 \times 17^6$. How many positive factors of $N^2$ are less than $N$ but not a factor of $N$?

Let $N$ = $11^2 \times 13^4 \times 17^6$. How many positive factors of $N^2$ are less than $N$ but not a factor of $N$? $Approach$: $N$=$11^2$.$13^4$.$17^6$ $N^2$=$11^4$.$13^8$.$17^{12}$ This ...
1
vote
1answer
54 views

How many $(x,y)$ satisfy this?

How many pairs $(x,y)$ of positive integers with $x\leq y$ such that $GCD(x,y) = 5!$ and $LCM(x,y) = 50! $ ??
1
vote
1answer
75 views

Coding a sequence into a natural number by map $f$ with $f(k_1, .., k_n) + f(k_{n+1}, .., k_{2n}) = f(k_1 + k_{n+1}, .., k_n + k_{2n})$

Has anyone discovered a way of coding a sequence of natural numbers into a natural number by map $f$ that has the following property $f(k_1, .., k_n) + f(k_{n+1}, .., k_{2n}) = f(k_1 + k_{n+1}, .., ...
1
vote
2answers
63 views

How to find $a,b\in\mathbb{N}$ such that $c = \frac{(a+b)(a+b+1)}{2} + b$ for a given $c\in\mathbb{N}$

Suppsoe that $$c = \frac{(a+b)(a+b+1)}{2} + b$$ Now $c$ is given - how does one find satisfying $a, b$?
1
vote
1answer
86 views

Proof of Generalized Primorial Primes

Let's call the numbers of the form $k\times p\# \mp1$, the Generalized Primorial Primes. One can find many $k$ for a fixed $p$ such that $k\times p\# \mp1$ be prime. As an example for $p = 8933$ ...
1
vote
1answer
51 views

Inequality involving primes

Suppose that $p,q$ and $r$ are primes such that $p>q>r$, and $kp+1$ divides $qr$ for some $k\neq 0$. Then $1+kp=qr$. I really need help on this. Any hint how to establish this? Thank you.
1
vote
1answer
205 views

Composition of Injective and Surjective maps? [closed]

Consider a composite $f \circ g(x) = f(g(x))$ of two maps $X \xrightarrow{g} Y \xrightarrow{f} Z$. If $f$ is injective and $g$ is surjective, what is the results of the composition $f \circ g$? [or ...
1
vote
2answers
650 views

Solving non-linear congruence

$x^2+2x+2\equiv{0}\mod(5)$, $7x\equiv{3}\mod(11)$ My attempt: $x^2+2x+2\equiv{0}\mod(5)$ $(x+1)^2\equiv-1\mod(5)$, we have $x+1\equiv-1\mod(5)$ since $5$ and $11$ are coprime. We have a solution ...
1
vote
1answer
116 views

Proving $g(\chi\rho)^6=(-1)^{(p-1)/2}p(\overline{\chi(2)J(\chi,\rho)})^4$, from Ireland and Rosen.

Suppose $p\equiv 1\pmod{3}$, $\chi$ is a cubic character, and $\rho$ is the quadratic character on $F_p$. If $\chi\rho$ is a character of order $6$, why does the Guass sum ...
1
vote
1answer
82 views

Show that the $\mathbb{Z}$-span $\mathbb{Z}b'_1+\cdots+ \mathbb{Z}b'_d$ of $B^+$ does not depend on the choice of $B$

Let $K$ be a number field, let $\mathcal{O}_K$ be its ring of integers, and let $B = \{b_1,\ldots,b_d\}$ be a subset of $K$ of cardinality $d$ such that $\mathcal{O}_K = ...
1
vote
1answer
103 views

Application of the fundamental theorem of algebra

I'm just going through my lecture notes and under one subheading "application", I have written: If $m = \prod_{i = 1}^k p_i^{r_i}$ and $n = \prod_{i = 1}^k p_i^{s_i}$, for primes $p_i$ & $r_i, ...
1
vote
2answers
152 views

Finite fields are isomorphic

This is from A Course in Arithmetic by JP Serre Theorem 1 ii) Let $p$ be a prime number and let $q = p^f(f \geq 1)$ be a power of $p$. Let be an algebraically closed field ...
1
vote
2answers
47 views

Explaining how $n = 2^r$ for $n$ prime

I found this claim in my textbook while reading the section on prime numbers today: "If $n$ is a positive integer such that $2^n + 1$ is prime, then $n = 2^r$ for some integer $r \ge 0$." Where did ...
1
vote
3answers
105 views

bound for the product of numbers

Let $n \in N$. Fix $m \in [-n,n]$. I am curious, how to bound from above the following expression $$ (n-m)^{\frac{n-m}{2}+1}(n+m)^{\frac{n+m+1}{2}}\leq \quad ? $$ Thank you.
1
vote
1answer
41 views

Primes of the form $16\cdot m^{2}+31\cdot m$

How would I determine all primes of the form $16\cdot m^{2}+31\cdot m$. And in general how do you determine primes of various forms.
1
vote
1answer
74 views

generalization of base-n notation from naturals to fractions

not exactly sure how to best ask this. base-$n$ notation involves a series of digits written where each digit is a natural number less than $n$. is there some math/theory generalization of ...
1
vote
5answers
100 views

polynomial of degree at least 1

I was told to assume $f(x)$ is a polynomial with degree $d\geq 1$ with integer coefficients and positive leading coefficient. (i) I need to show that there are infinitely many $x$ such that $f(x)$ ...
1
vote
2answers
139 views

What is the solution number of the equation $x^2-x+1\equiv 0 \pmod{p^e}$

What is the solution number of the equation $$x^2-x+1\equiv 0\pmod{p^e}$$ I know when $e=1$, it is $1+\left(\frac{-3}{p}\right)$, and I guess it is the same for $e>1$, but can anyone provide a ...
1
vote
1answer
90 views

Norm in $\mathbb{R}/\mathbb{Z}$

I have to prove some statements about some norm in $\mathbb{R}/\mathbb{Z}$, for example "Let $x$, $y$, $z$ be points in $\mathbb{R}/\mathbb{Z}$ such that x + y + z = 0. Prove that one of the options ...