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
2answers
39 views

Find a non-trivial solution for the Diophantine Equation $17a^4 + 5b^4 = 35c^4$, or show that no non-trivial solutions exist

This is a problem on my practice exam for number theory, and we haven't had an example like this in class yet. The question is looking for a solution in $\mathbb{Z}$ for $a,b,c \in \mathbb{Z}$. I've ...
0
votes
0answers
11 views

How can I apply binomial expansion to $(x^2-D)^{p-1\over 2}$?

I am trying to show that $(x^2-D)$ is a square (modp). I have noticed that the legendre symbol is equivalent to saying $(x^2-D)^{p-1\over 2}$(modp). I have been told I can apply binomial expansion to ...
0
votes
0answers
6 views

Stern Brockott tree and relative primality

I'm reading through chapter on Number Theory on "Concrete Mathematics" and there is a snippet about Stern-Brockott tree (http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree) and I'm trying to ...
4
votes
1answer
33 views

Sum of elements of a finite Field

Let $F$ be a finite field and $i$ an integer. Calculate the sum of all the elements of $F$,each raised to the $i-th$ power. My approach so ...
0
votes
1answer
27 views

Find the increasing function where $g_4 : \mathbb N^4 \to\mathbb N$, $(a, b, c, d) \mapsto 2^{a−1}3^{b−1}5^{c−1}h_4(d)$

A bijection $g_4 : \mathbb N\times \mathbb N \times\mathbb N \times\mathbb N \to\mathbb N$, with $$(a, b, c, d) \mapsto 2^{a−1}3^{b−1}5^{c−1}h_4(d)$$ is constructed, with $h_4(d)$ as an increasing ...
0
votes
1answer
33 views

Find a function h3(c) that will make $ (a, b, c) \mapsto 2^{a−1}3^{b−1}h_3(c)$ a bijection [on hold]

Find a function $h_3(c)$ that will make $$g_3 : \Bbb N × \Bbb N × \Bbb N → \Bbb N, \qquad (a, b, c) \mapsto 2^{a−1}3^{b−1}h_3(c)$$ a bijection. Your $h_3(c)$ should be an increasing function, i.e. ...
6
votes
2answers
40 views

Quadratic Reciprocity

I've been asked to see if $x^2\equiv83$ $(\mathrm {mod} \ 101^{2000})$ has solutions. Now I know $x^2\equiv(\mathrm{mod} \ 101)$ has no solutions since the quadratic reside symbol ...
3
votes
1answer
33 views

why does exist infinite postive $k$, such $\lfloor \frac{n^k}{k}\rfloor$ is odd numbers

Give the postive integer $n>1$, there exist infinite positive integer $k$ such $\lfloor \dfrac{n^k}{k}\rfloor$ is odd Maybe can Use Euler's theorem,$$n^{\phi{(k)}}\equiv 1\pmod k$$ let ...
4
votes
1answer
50 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$, ...
-3
votes
1answer
33 views

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

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
2answers
63 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
40 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
19 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
45 views

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

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
23 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
52 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
24 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
22 views

Quadratic residue dependency on $\bmod 4$ [duplicate]

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
31 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
45 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
34 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
13 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
18 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 ...
0
votes
1answer
31 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.
3
votes
1answer
29 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
11 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
29 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
1answer
28 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
28 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
54 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
48 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
34 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
16 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
86 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
46 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
47 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
52 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
46 views

-a is also a quadratic residue mod p [on hold]

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
24 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
26 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
27 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
54 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
33 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 ...