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)

3
votes
0answers
17 views

Solve in positive integers: $5x^2+6x^3=z^3$

Solve in positive integers: $5x^2+6x^3=z^3$. $x^2(6x+5)=z^3$ If $(x,5)=5$, let $x=5k$. So $k^2(6k+1)=\left(\frac{z}{5}\right)^3$, we're left with solving $6n^3+1=m^3$. If $(x,5)=1$, ...
-1
votes
1answer
24 views

Show that $1^n+2^n+\cdots+(p-1)^n\equiv 0\pmod {\!p}$

Let $p$ be an odd prime, and let $n$ be an integer not divisible by $p-1$. Show that $$1^n+2^n+\cdots+(p-1)^n\equiv 0\pmod {\!p}$$
0
votes
1answer
45 views

Prove that for any prime p, there are integers x and y such that $p|(x^2+y^2+1)$

I asked this question a couple days ago, Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $. but as I asked it as a guest, I could not comment on the ...
0
votes
1answer
35 views

show $p$ is divisible by $(x^2 +y^2 +1)$ [duplicate]

Show that, for any prime $p$, there are integers $x$, and $y$ such that $p$ is divisible by $(x^2+y^2+1)$ Can you show me what to start with? do I prove $p$ is divisible by $x^2$ and $y^2$ ...
0
votes
1answer
16 views

calculation a Legendre symbol with reciprocity

evaluate the following Legendre symbol using quadratic reciprocity (295/401) (713/1009) I know that can flip the numbers and reduce because both 401 and 1009 are 1 mod p and so on, but I am ...
-1
votes
3answers
36 views

show that $3^{(p-1)/2} +1$ is divisible by $p$

let $n$ be an integer $>1$, and suppose that $p=2^n+1$ is a prime. Show that $3^{(p-1)/2} +1$ is divisible by $p$ (First show that $n$ must be even)
0
votes
0answers
18 views

Number of representations of sums of four squares?

I was told that multinomial expansion can be used to determine how many representations of four squares a number like 53 has? I have a number theory textbook and have done some googleing neither has ...
2
votes
1answer
41 views

$\displaystyle\prod_{ p\leq x}p\leq 4^{x-1}$ for all real $x\geq2$

How yo prove this? I'm looking the Erdös proof from Bertrand Postulate and there are many things I don't get. Please don't hints, I'm newbie in combinatorics techniques. In the book I don't get how ...
1
vote
1answer
21 views

Proving consecutive quadratic residue modulo p [duplicate]

Let p be a prime with p > 7. Prove that there are at least two consecutive quadratic residues modulo p. [Hint: Think about what integers will always be quadratic residues modulo p when p ≥ 7.]
-1
votes
0answers
21 views

Quadratic residue dependency on $\bmod 4$

Let $p$ be an odd prime and let $a$ be a quadratic residue modulo $p$. Write a formal proof showing that $−a$ is also a quadratic residue modulo $p$ if and only if $p ≡ 1 \bmod 4$. I sort of ...
1
vote
0answers
22 views

Irreducible Polynomial-Am I doing this wrong?

Ok,this problem might appear a bit trivial but I have some doubts..If it's not a burden take a look and comment! Let $F$ be a finite field of characteristic equal to $p$ and $ƒ(x)=x^p-α$ $∊F[x]$.Show ...
0
votes
2answers
34 views

Smallest odd number n such that $2^n-1$ is divided by twin primes.

This is a problem from Elementary Number Theory by Burton (7th ed.) I am finding the smallest odd number n such that $2^n-1$ is divided by twin primes $p$ and $q$, where $3 < p < q$. I followed ...
1
vote
1answer
33 views

How to find p+q = sum, where p and q are distinct primes?

I have been given $\phi(m)$ and $m = pq$. Because $p$ and $q$ are primes, $\phi(m) = (p - 1)(q - 1)$ So I was able to find that $p+q$ = sum But how do I find $p$ and $q$ after this? The sum is larger ...
1
vote
1answer
10 views

Torus translation is ergodic if and only if the components of the translation vector are rationally independent.

I'm reading Ergodic Theory and Differential Dynamics by Ricardo Mane. There is a theorem in the book that states the following: If x $\in$ $R^n$, the translation L $_{\pi(x)}$: $T^n \rightarrow T^n$ ...
0
votes
1answer
12 views

Question involving DES cryptosystem

This is probably an easy question. Im Assuming whoever can answer this has access to S-boxes and P boxes etc. Suppose the input to a round of DES is 1010101010......10101010. (64 bits) Suppose the ...
0
votes
1answer
29 views

Number Theory, using order of integers

I have $k = 37$ and $m = 101$ How do I find $a$, given the value of $a^k \bmod m$? I think this has to do with order of integers.
2
votes
0answers
15 views

Show that $α$ is a perfect square in the quadratic integers in $\mathbb Q[\sqrt{d}]$

Question: Suppose that $\mathbb Q[\sqrt{d}]$ is a UFD, and $α$ is an integer in $\mathbb Q[\sqrt{d}]$ so that $α$ and $\barα$ have no common factor, but $N(α)$ is a perfect square in $\mathbb Z$. How ...
0
votes
1answer
23 views

Largest common divisor

Show that each common divisor $c_1 , \ldots , c_n \in \mathbb{Z}$ divides their largest common divisor. Use subgroups of the group $ \mathbb{Z}$. Could somebody help me? Please
0
votes
0answers
9 views

Torelli Shanks Algorithm - Repeated Squarring Method

This algorithm is using when you want to find a square root of a number in a given moduli. I can't see the idea behind this algorithm, so can someone explain it in a simple way?
0
votes
0answers
27 views

An interesting property of curves $V:$ $x^3$ + $y^3$ = A$z^3$

Let $V$ be the elliptic curve V: $x^3$+ $y^3$ = A$z^3$ where A > 2 is cube free natural number. A conjugate quadratic point of $V$ is one of the form $(a + b\sqrt d, a - b\sqrt d, c)$ (note that all ...
0
votes
0answers
20 views

Find the set of primes p for which -3 is quadratic residue mod p

Find the set of primes $p$ for which $-3$ is quadratic residue $\text{mod } p$. I have started my solution like this: $1= \left(\dfrac{-3}{p}\right) = ...
3
votes
0answers
22 views

Number field attached to a finite group.

Let $G$ be a finite group. I know that the set of irreducible representations of $G$ over the complex numbers (up to isomorphism) is finite. Let us fix our attention on some irreducible ...
1
vote
2answers
51 views

About primes and Euler's totient function.

Is the number of primes $< n$ itself less than the number of positive integers that are less than $n$ and relatively prime to $n$?
0
votes
1answer
42 views

Squares in a Finite Field

Show that in any finite field,each of its elements can be written as the sum of two squares. Well,I hate to admit-this being also my first post-that I have not proven it yet.I tried to work on the ...
2
votes
1answer
21 views

Why is $\sum_{x=1}^{p-1}\left(\frac{x}{p}\right)=\left(\frac{0}{p}\right)$

For $p$ an odd prime, Why is $$\sum_{x=1}^{p-1}\left(\frac{x}{p}\right)=\left(\frac{0}{p}\right)$$ where $\left(\frac{x}{p}\right)$ is the Legendre symbol. I'm not sure if I have given enough ...
0
votes
1answer
32 views

Is it possible to bound recurrence functions for primes?

Would it be possible to bound this function for primes in terms of the maximum difference between the images of the function and their closest primes (for instance, the fifth term is 33 and has ...
0
votes
0answers
19 views

Simple Number Theory Problem Congruences

If I have the following congruence: $x^2 \equiv a \pmod {p^2}$ where p is an odd prime and (a,p)=1 , how do I know that (x,p)=1 ?
0
votes
0answers
15 views

How many kind of basis function to approximate an arbitrary function

I am finding a list algorithm to approximate an arbitrary function. Such as Bernstein, he said that a linear combination of Bernstein basis polynomials $$B_n(x) = \sum_{\nu=0}^{n} \beta_{\nu} ...
1
vote
2answers
84 views

Why study Lowest Common Multiple - LCM

What is the most motivating way to introduce LCM of two integers on a first elementary number theory course? I am looking for real life examples of LCM which have an impact. I want to be able to ...
0
votes
1answer
38 views

Difference between generalized cuban primes and cuban primes.

I have been studying cuban primes and while the official definition of cuban primes contains only two variations, I have also seen a reference to generalized cuban primes, which has a much larger set. ...
0
votes
0answers
42 views

Every element in a finite field E is a sum of 2 squares. [on hold]

I have a exercise of field. Prove that every element in a finite field E is a sum of 2 squares (if z = $a^2$ then we can write z = $a^2 + 0^2$. I have tried to use a quadratic residue but no result.
-1
votes
2answers
42 views

$x^2 \equiv a$ mod p, $x^2 \equiv b$ mod p, and $x^2 \equiv ab$ mod p, prove either all three are solvable or exactly one

Let p be an odd prime and a, b ∈ Z with p doesn't divide a and a doesn't divide b. Prove that among the congruence's $x^2 \equiv a$ mod p, $x^2 \equiv b$ mod p, and $x^2 \equiv ab$ mod p, either all ...
-3
votes
3answers
50 views

Is $ n^{2} + 1 $ divisible by $ 7 $? By $ 13 $?

1) Does there exist a positive integer $ n $ such that $ n^{2} + 1 $ is divisible by $ 7 $? Prove assertions. 2) Does there exist a positive integer $ n $ such that $ n^{2} + 1 $ is divisible by $ 13 ...
-1
votes
2answers
43 views

-a is also a quadratic residue mod p

Let p be an odd prime and let a be a quadratic residue modulo p. Prove that −a is also a quadratic residue modulo p if and only if p ≡ 1 mod 4.
1
vote
2answers
23 views

Number of solutions to congruences

Is there any general form to determine the number of non-congruent solutions to equations of the form $f(x) \equiv b \pmod m$? I solved a few linear congruence equations ($ax \equiv b \pmod m$) and I ...
1
vote
2answers
25 views

Show the number of quadratic residues $a$ modulo $p$ with $1\leq a\leq p-1$ is $(p-1)/2$

Question: When $p$ is an odd prime, show that the number of quadratic residues $a$ modulo $p$ with $1\leq a\leq p-1$ is $(p-1)/2$ Answer: From Euler's criterion $\left(\frac{a}{p}\right)\equiv ...
1
vote
0answers
23 views

Show $\text{Gal}(K_\infty/\mathbb Q)\cong \mathbb Z_p^{\times}$

Let $\zeta_{p^n}$ be the primitive $p^n$-th root of unity where $p$ is a prime and $K_n=\mathbb Q(\zeta_{p^n})$ the $p^n$-th cyclotomic field. Let $K_\infty=\bigcup K_n$. Could someone give a proof ...
0
votes
1answer
17 views

Solving recurrence with moebius inversion

what's up folks? I'm solving the red book of math problems, problem 16 which is to solve the following recurrence relation: $\sum_{k=1}^n {n \choose k} a(k) = \frac{n}{n+1}$ PS: ${n \choose k} = ...
0
votes
0answers
20 views

Finding the m-th coefficient of an equation

Does anyone know how to find the m-th coefficient of $-t=(3+2\sum_{k=1}^{\infty} \frac{t^{2k}}{(2k)!})(\sum_{n=0}^{\infty} D_n \frac{t^n}{n!})$? The answer is: $0=3 \frac{D_m}{m!}+2\sum_{k=1}^{m/2} ...
2
votes
2answers
36 views

if $P$ is a prime ideal of $O_K$, then $O_K/P$ is finite

let $P$ be a non-zero prime ideal of $O_K$, where $K$ is a number field(i.e. the degree $[K:\mathbb{Q}]$ is finite) then $O_K/P$ is finite. I'm working through a proof for this claim, however there is ...
0
votes
2answers
50 views

Show that $f(a)$ converges after some point

There is a row of 1000 integers. There is a second row below, which is constructed as follows. Under each number $a$ of the first row, there is a positive integer $f(a)$ such that $f (a)$ equals ...
-1
votes
1answer
32 views

Is $\pi(y)\pi(x+k)\ge\pi(x)\pi(y+k)$? [on hold]

Is it true that for some fixed $k\ge2$ and for all sufficiently large $x$ and $y$ with $y\ge x$ we have, $$\pi(y)\pi(x+k)\ge\pi(x)\pi(y+k)$$ where $\pi(x)$ is the prime counting function. I am ...
5
votes
0answers
28 views

$\sum_{n=1}^{\infty}\frac{a_n}{10^n}$ where $\{a_n\}_{n=1}^{\infty}$ is a sequence in the ten digits {0, 1, 2 , 3 , 4 , 5 , 6 , 7 , 8 ,9}

Let $\{a_n\}_{n=1}^{\infty}$ be a sequence in the ten digits {0, 1, 2 , 3 , 4 , 5 , 6 , 7 , 8 ,9} And consider the sum $\sum_{n=1}^{\infty}\frac{a_n}{10^n}$ $\in$ $[0,1]$ What characteristics of ...
0
votes
0answers
17 views

Algebra inequality problem

Suppose: $ x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 1$ , and $x_1x_3x_5 + x_2x_4x_6 \ge \dfrac {1}{540} $ and $\dfrac{p}{q}$ is the maximum possible value of $x_1x_2x_3 + x_2x_3x_4 + x_3x_4x_5 + x_4x_5x_6 ...
0
votes
2answers
44 views

If $ p $ is an odd prime and $ D $ an integer not divisible by $ p $, show that $ x^2 - y^2 \equiv D ~ (\text{mod} ~ p) $ has $ (p - 1) $ solutions.

I am supposed to have proved the following congruence identity: $$ 1^{n} + 2^{n} + \cdots + (p - 1)^{n} \equiv 0 ~ (\text{mod} ~ p). $$ This is apparently meant to help me solve the problem stated in ...
0
votes
1answer
17 views

Does $cN \leq \left|\sum_{n= 1}^{N}f(n)\right|$ imply $|f(n)| \geq c/2$ for many $n$?

Let $f: \mathbb{N}\rightarrow \mathbb{R}$ be a function potentially taking negative values. Suppose I knew that $$cN \leq \left|\sum_{n= 1}^{N}f(n)\right|$$ for some absolute constant $c$. Then by the ...
0
votes
0answers
24 views

Prove that if $x^3 + y^3 = z^3$, and $x$, $y$, $z$ are quadratic integers in $\mathbb Q[\sqrt{−3}]$, then $λ$ must divide one of $x$, $y$, or $z$.

Let $λ = (3 + \sqrt{−3})/2 ∈ Q[\sqrt{−3}]$. Prove that if $x^3 + y^3 = z^3$, and $x$, $y$, $z$ are quadratic integers in $\mathbb Q[\sqrt{−3}]$, then $λ$ must divide one of $x$, $y$, or $z$.
1
vote
1answer
36 views

Prove by counterexample that $\gamma$ and $\delta$ are not necessarily unique

Assume $\mathbb Q[\sqrt{d}]$ is a Euclidean Field and $\alpha$, $\beta$ are two quadratic integers in $\mathbb Q[\sqrt{d}]$, so that there exists integers $\gamma$ and $\delta$ in $\mathbb ...
2
votes
2answers
46 views

How to smoothly approximate a sign function

I have a function that defined as following $$f(x) = \begin{cases} 1, & \text{if $x > 0$ } \\ 0, & \text{if $x=0$ } \\ -1, & \text{if $x<0$ } \end{cases}$$ In practice, the $f(x)$ ...
1
vote
0answers
19 views

Apply the Euclidean algorithm to $2$ and $1 − 3i$ in the integers of $\mathbb Q[\sqrt {-1}]$

Question: I have to apply the Euclidean algorithm to $2$ and $1 − 3i$ in the integers of $\mathbb Q[\sqrt {-1}]$ My Solution: Since $N(2) = 4$ and $N(1–3i) = 10,$ we must start by dividing $1–3i$ ...