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

Intuitive explanation for this Gamma function identity

Wolfram Alpha says that this result is true: $$\frac{\Gamma(n+1)}{\Gamma(\frac{n}{2}+1)} = \frac{\Gamma(\frac{n}{2} +\frac{1}{2})}{\Gamma(\frac{1}{2})} \times 2^n$$ This implies a curious result for ...
4
votes
0answers
35 views

Carmichael numbers of form $m^3+1$ and Ramanujan's $1729$

While researching for a post on tetranacci pseudoprimes I came across a list of Carmichael numbers, $$C_n = 561,\, 1105,\, 1729,\, 2465,\, 2821,\dots$$ Of course, Ramanujan's taxicab number $1729 = ...
2
votes
1answer
17 views

Why $\ker N_{E/F}$ is a map from $E^{\times}$ to $F^{\times}$?

I am reading the lecture notes. In the end of page 1, it is said that $\ker N_{E/F}$ is a map from $E^{\times}$ to $F^{\times}$. Here $E/F$ is a quadratic field extension. Let $\alpha \in E$ and ...
1
vote
3answers
27 views

How to prove a Fibonacci inequality using Strong Induction?

Using strong induction I am trying to prove that $$F_n \geq \left(\frac{1+\sqrt{5}}{2}\right)^{n-2} \text{ for all } n \geq 2$$ for the Fibonacci Sequence defined by: $F_0 = 0$, $F_1 = 1$, and $F_n ...
0
votes
1answer
16 views

Prove that if $\{1^5,2^5,\ldots, (pq)^5\}$ is a complete residue system mod $pq$, then $\{1^5,2^5,\ldots,p^5\}$ is too, mod $p$

$p,q\ge 2$ are coprime positive integers. Prove that if $\{1^5,2^5,\ldots, (pq)^5\}$ is a complete residue system mod $pq$, then $\{1^5,2^5,\ldots,p^5\}$ is a complete residue system mod $p$. ...
-1
votes
0answers
30 views

Let $p$ be an odd prime, $D$ be an integer not divisible by $p$. show that $x^2 - y^2 = D (\text{mod } p)$ has $(p-1) $solutions [duplicate]

Let $p$ be an odd prime, $D$ be an integer not divisible by $p$. Show that $$ x^2 - y^2 = D \bmod p $$ has $p-1$ solutions Can somebody help with this problem? Thank you!
0
votes
1answer
32 views

Solutions of the Pell Equation $x^2-2y^2=-1$

I am assigned to find solutions to the Pell-type equation. $x^2-2y^2=-1$ So far, I only have $(7,5), (41,29)$ and $(239,169)$. My question is, is there a general formula to find all its solution? ...
2
votes
1answer
13 views

Division of the Binomial Coefficient

Prove that when p is prime, the binomial coefficient p!/(r!)((p-r)!) is divisible by p with r being greater than or equal to 1 and less than or equal to p-1 . Clearly p! is divisible by p so I cant ...
3
votes
0answers
16 views

exponential sum estimate involving Von Mangoldt function

Let $f(x)$ be a polynomial. Define $$ S(\alpha) = \sum_{1 \leq n \leq N} e^{2 \pi i f(n) \alpha}. $$ I was wondering how does one obtain that $$ \left( \int_0^1 S(\alpha) \ d \alpha \right)^2 \leq ...
3
votes
2answers
61 views

How to populate a $0-$line with $1$'s?

I have a line of $n$ $0$'s like this: Zeroth index -->$000...000$ I want to populate the line with $m$ $1$'s with the following rules: (1) They have to occur after the index ...
1
vote
0answers
29 views

Fermat's last theorem generalization

Are there solutions to Fermat's last theorem in transcendental numbers greater than two, for further details please follow the link below: http://www.quora.com/What-is-the-new-Pythagoras-Theorem Let ...
1
vote
3answers
26 views

Prove there exists $m$ and $k$ such that $ n = mk^2$ where $m$ is not a multiple of the square of any prime.

For any positive integer $n$, prove that there exists integers $m$ and $k$ such that: $$n = mk^2 $$ where $m$ is not a multiple of the square of any prime. (For all primes $p$, $p^2$ does not divide ...
4
votes
2answers
49 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
1answer
9 views

Stern-Brocot tree and relative primality

I'm reading through chapter on Number Theory on "Concrete Mathematics" and there is a snippet about Stern-Brocot tree and I'm trying to understand why exactly all fractions in the tree are ...
4
votes
1answer
39 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
28 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
42 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
37 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
51 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
36 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
74 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
44 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
20 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
48 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
53 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
25 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
32 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
35 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
14 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
20 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
24 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
29 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
55 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
50 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
35 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
90 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
39 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
47 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 ...