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)

0
votes
2answers
21 views

divisibility of complex numbers

So for the firs tpart do I just multiply two complex numbers together then square it? Can this idea be used for the other parts of this problem as well? The help would be appreciated!
2
votes
2answers
52 views

Compute the values of two infinite products whose factors are the same

I have the following question: How to prove that $(1-\frac{1}{2})\cdot (1+\frac{1}{3})\cdot (1-\frac{1}{4})\cdot (1+\frac{1}{5})\cdot (1-\frac{1}{6})\cdot (1+\frac{1}{7})\cdot ...
3
votes
2answers
199 views

Is this a meaningful approach to primes?

Motivation: I tend to be good at recognising patterns and I saw one with factorial: $$ n! = \prod_{i=1} p_i^{J(n,p_i)} $$ where $p_i$ is the $i$'th prime and $$ J(n,i)= \sum_{S=1}^\infty [n/i^S] $$ ...
2
votes
2answers
26 views

Number Theory Simple Proof

I am looking at a solution for a problem where the following line is stated but not explained, and I can not seem to make sense of it: If a prime $p\equiv 3\pmod 4$ then why is $\frac{p(p+1)}{2}$ ...
3
votes
1answer
54 views

How to define multiplication in $\mathbb{Z}$ with divisibility and addition?

Q: Show that $(\mathbb{Z},|,+,0,1)$ defines multiplication in $\mathbb{Z}$. I know how to do this in $\mathbb{N}$, but I'm stuck trying to do this is $\mathbb{Z}$. The idea I have is to define lowest ...
5
votes
1answer
100 views

With $N$ a constant $>0$, show $\prod_{p<x}\frac{1}{p^{N+1}-1}>\frac{0.2}{\log^2 x}$.

Related. Show that if $x$ is large enough,$$\prod_{\substack{p<x \\ p \ \text{prime}}}\frac{1}{p^{N+1}-1}>\frac{0.2}{\log^2 x}.$$ Speaking of which, Theorem 6.12, and maybe others, of this ...
0
votes
0answers
12 views

Solving quadratic congruences?

I am having trouble learning to solve quadratic congruences. I need to solve $$ x^2=317\pmod{ 77747} $$ using two different methods. Setting up in an index table isn't feasible since $p$ is so ...
3
votes
1answer
32 views

How to decide which number's modulo should be checked?

Consider the following question Find all integer solutions to $y^2 = x^5 - 4$. The solution goes something like - check modulo 11, $x^5 \equiv 1,-1$ and check cases to arrive at the conclusion ...
3
votes
2answers
46 views

If $m, n$ be positive integers, prove that $\phi(mn)=\phi((m,n))\phi([m,n])$, where $(m,n)=$ gcd of $m, n$ and $[m, n]=$ lcm of $m, n$.

If $m, n$ be positive integers, prove that $\phi(mn)=\phi((m,n))\phi([m,n])$, where $(m,n)=$ gcd of $m, n$ and $[m, n]=$ lcm of $m, n$. I have no idea to solve this question. Please help me to ...
1
vote
1answer
46 views

Solviang a Diophantine equation:$y^x=x^{2007}$($x$ and $y$ integers).

I found this Diophantine equation and to solve it I used the definition of logarithm but the solution doesn't need of the use of logarithmic rules. I solved it in this way: $$y^x=x^{2007}$$ ...
8
votes
2answers
198 views
+500

Fermat's last theorem and $\mathbb{Z}[\xi]$

I heard that one can prove special cases of FLT by using unique factorization in $\mathbb{Z}[\xi]$ (whenever this is possible), where $\xi$ is a primitive $n$-th root of unity. How can one do this in ...
-2
votes
1answer
67 views

Cantor's Diagonal: Why not a 1-2 Correspondence between the Naturals and Reals?

Hopefully I'm following Cantor's Diagonal Argument with a minimum of distortion and omission: We start from an enumeration T of all infinite binary sequences. We then construct a list S of elements ...
0
votes
1answer
24 views

Primitive root problem

Let $p>3$ be prime number and $a$ primitive root modulo $p^2$. Prove that $x^{p-1}\equiv 1 \pmod{p^2}$ solutions are $\overline{a}^p,\overline{a}^{2p},\ldots ,\overline{a}^{(p-1)p}$. Any ideas on ...
14
votes
2answers
402 views

Why is $(\sqrt{2}+\sqrt{3})^{2008}$ so close to an integer?

Using 5000-digit precision in PARI/GP, I discovered that the fractional part of $(\sqrt{2}+\sqrt{3})^{2008}$ is extremely small, less than $10^{-999}$. Is there a simple explanation for this fact ? ...
1
vote
1answer
44 views

the blood test riddle (number theory)

A microbiologist has been given a set of $100$ blood vials. Exact one of those $100$ vials is positive to a concrete disease X. The microbiologist desires to send only $7$ vials for analysis. He can ...
6
votes
3answers
207 views

I finally understand simple congruences. Now how to solve a quadratic congruence?

Now that I have plain old congruences, $19x\equiv 4 \pmod {141}$ for example, I am trying to wrap my brain around quadratic ones. My textbook shows how to tackle the aforementioned congruences, but ...
2
votes
0answers
30 views

Runs of consecutive numbers all of which are rebel numbers

A positive integer is said to be a rebel number if it is the product of numbers none of which share any of the original number´s digits. Thus 10 = 2 x 5 is a rebel number, while none of the primes is. ...
1
vote
0answers
23 views

Is the discriminant of a polynomial surjective onto $\mathbb Z$?

Consider polynomials of degree two over $\mathbb Z$: $f = ax^2+bx+c$ The discriminant is $D = b^2-4ac$ And we can show that $D=2$ is not a possible value for $D$. I wonder if the value $D=2$ ...
3
votes
4answers
78 views

If $a,b$ are positive rational numbers and $\sqrt a+\sqrt b$ were rational, then both of $\sqrt a,\sqrt b$ are rational numbers

I'm trying to show that If $a,b$ are positive rational numbers and $\sqrt a+\sqrt b$ were rational, then both of $\sqrt a,\sqrt b$ are rational numbers. I squared the number $\sqrt a+\sqrt b$ ...
3
votes
1answer
203 views

What is the sixth Martin quadruple $\sqrt[n]{x_1^k+x_2^k+x_3^k+x_4^k} =\text{Integer}$ for $k=1,2,3$?

Define a Martin quadruple {a,b,c,d} as a solution in non-zero integers to the system, $a+b+c+d = x^2$ $a^2+b^2+c^2+d^2 = y^2$ $a^3+b^3+c^3+d^3 = z^3$ It can be shown that there are an infinite ...
0
votes
2answers
31 views

Standard result for $\log(x)$

$$\sum_{1\leq m\leq x/d}\frac{1}{m}=\log(\frac{x}{d})+O(1)$$ I read this result in lecture papers I was going through and can't find anything about its origin. Is there a standard summation result ...
2
votes
0answers
7 views

Town Network - Show there is a Tetrahedron of the Same Transport

Question: There are 18 towns such that between each pair of towns there is either a train or bus service (not both). Prove that there are 4 towns such that all 6 of their pairwise connections use the ...
1
vote
3answers
27 views

Divisibility of integers by integers

We are given a number $$K(n) = (n+3) (n^2 + 6n + 8)$$ defined for integers n. The options suggest that the number K(n) should either always be divisible by 4, 5 or 6. Factorizing the second bracket ...
0
votes
1answer
35 views

The genus of a certain kind of cubic

I have a cubic curve that looks like $$ a_0 x^3 + a_1 x^2 y + a_2 xy^2 + a_3 y^3 = b $$ with $a_0, a_1, a_2, a_3$, and $b$ all integers, and $a_0$ and $b$ nonzero. I'm not sure but I think in my ...
10
votes
4answers
360 views

Understanding the trivial primality test

I'm reading an algorithms book and I came across a code example for a primality test. The problem is that I couldn't understand the condition for the for-loop: ...
0
votes
1answer
21 views

Arithmetic functions proof

Theorem: Let $f$ be an arithmetic function such that $f(1)=1$. Then there exists a unique arithmetic function $g$ such that $f\ast g =\epsilon$. The arithmetic function $g$ is called the Dirichlet ...
0
votes
2answers
22 views

Mistake in proof of sum of divisors function $\sigma(n)$

The proof derives the correct result, but I cannot see how the first equality is correct. To begin we use the formula $\sigma(n)=\sum_{d\mid n}d$ This is the first step in the proof: $$\sum_{1\leq ...
21
votes
3answers
2k views

Why doesn't $0$ being a prime ideal in $\mathbb Z$ imply that $0$ is a prime number?

I know that $1$ is not a prime number because $1\cdot\mathbb Z=\mathbb Z$ is, by convention, not a prime ideal in the ring $\mathbb Z$. However, since $\mathbb Z$ is a domain, $0\cdot\mathbb Z=0$ is ...
0
votes
2answers
33 views

If every prime that divides $n$ also divides $m$, show that $\phi(mn)=n\phi(m)$ and $\phi(mn)=m\phi(n)$

If every prime that divides $n$ also divides $m$, show that $\phi(mn)=n\phi(m)$ and $\phi(mn)=m\phi(n)$. My attempt. As every prime that divides $n$ also divides $m$, this implies that $(m,n)=d$ ...
1
vote
0answers
5 views

Is every Pisot-like integer the product of a Pisot integer and a root of unity?

For lack of better terminology, let's call an algebraic number $\beta$ Pisot-like if $|\beta| > 1$ and all its conjugates lie inside the complex unit circle (here $|\cdot|$ is the usual absolute ...
3
votes
2answers
91 views

Diophantine Equations : Solving $a^2$ $+$ $ b^2$ $=$ $2c^2$

I was working through some number theory problems , when I came across the following question : Find all solutions of $a^2$ $+$ $b^2$ $=$ $2c^2$ My Solution (Partial) : We can rewrite the ...
0
votes
1answer
12 views

Ideal factorization Theorem, more generally

Consider Theorem 4.3.1 in link (it's quite long, so please open the pdf) I'm wondering if we can assume that the prime ideal we want to decompose is not $(p)$ with $p$ a prime in $\mathbb Q$, but a ...
3
votes
1answer
29 views

Is there any solution to this quadratic Diophantine 3 variables equation?

Is it possible to find all positive integer triplets $(x,y,z)$ satisfying the parametric equation : $$x^2 + 2ax + y^2 + 2by = z^2 + 2cz$$ Here $a, b, c$ are fixed positive integers.
2
votes
1answer
20 views

How does $ \text{Gal}(K / k) $ act on ideles?

Let $K/k$ be cyclic of degree $N$, Galois group $G$. I want to define some action of $G$ on the group of ideles $J_K$ which commutes with multiplication. A natural way to do this is to take each ...
1
vote
0answers
14 views

Prove that the “additive” operation of the module($\mathbb{Z}_{p}^{*},\mathbb{Z}_{p-1},\cdot$) is continuous.

Consider the following module $\mathcal{M}=$($\mathbb{Z}_{p}^{*},\mathbb{Z}_{p-1},\cdot$) in which the "additive" operation is defined by normal multiplication in $\mathbb{Z}_{p}^{*}$ and scalar ...
2
votes
1answer
69 views

Asymptotics of $\sum_{\mathfrak{a}}\frac{n^{k-\epsilon}}{\mathfrak{N}\left(\mathfrak{a}\right)^{r\left(k-\epsilon\right)}}$

In this paper by Brian D. Sittinger, the following claim is made: For an algebraic number field $K$ with norm $\mathfrak{N}$, let $\epsilon=\left[K:\mathbb{Q}\right]^{-1}$. Then, taking the sum over ...
6
votes
1answer
156 views

Why is $2^{16}=65536$ the only power of $2$ less than $2^{31000}$ that doesn't contain the digits $1$, $2$, $4$ or $8$ in its decimal representation?

$65536$ is the only power of $2$ less than $2^{31000}$ that does not contain the digits $1$, $2$, $4$ or $8$ in its decimal representation. http://en.wikipedia.org/wiki/65536_%28number%29
-4
votes
0answers
28 views

Finding the modulo of 801 [on hold]

If $d_{k}(m)$ is the number of divisor of m that are congruent to $k$ modulo $4$. How can I find $d_{1}(801)$ and $d_{3}(801)$ .
0
votes
1answer
20 views

Sum-of-divisors determinant

Let $\sigma_k(n)=\sum_{d|n}d^k$ be the generalized sum-of-divisors function. Let $S_n$ be the matrix defined by $[S_n]_{ij}=\sigma_i(j)$. I read a comment somewhere that $$\det(S_n)=1!\cdot 2!\cdots ...
1
vote
2answers
19 views

base b expansion of real numbers

This is a problem in Zygmund's analysis book. It is intuitively very straightforward. However, I could not give a rigorous proof. I hope someone can show me how to prove this rigorously. Problem: ...
7
votes
1answer
63 views

If all the numbers $(1^\alpha,\,2^\alpha,\,3^\alpha,\,\dotsc)$ are integer, then $\alpha$ is an integer.

A theorem of Siegel asserts that If $\beta>0$ and $2^\beta,\,3^\beta,\,5^\beta$ are integers, then $\beta$ is an integer. The following result is a beautiful consequence of this theorem ...
1
vote
3answers
37 views

Divergence of sum reciprocal of primes using Bertrand's Postulate

I have been trying to prove that the series of reciprocal of primes diverges by only using Bertrand's Postulate. Does anybody know if this is possible? Or is it the case that this postulate is not ...
7
votes
3answers
514 views

Is there any trivial reason for $2$ is irreducible in $\mathbb{Z}[\omega],\omega=e^{\frac{2\pi i}{23}}$?

This naive question came as the last problem in my homework. The author asked me to use linear relations of the discriminant like ...
2
votes
0answers
66 views

Class Group of $\mathbb Q(\sqrt{-15})$

Class Group of $\mathbb Q(\sqrt{-15})$ I used this paper for my attempt. First the discriminant of $\mathbb Q(\sqrt{-15})$ is the discriminant of the monic minimal polynomial of ...
0
votes
1answer
21 views

Solving an equation with complex numbers

I want to use complex numbers to solve the following problem: $x^2 = 95 - 168i$. I am sure there are a few ways of doing this but the way I want to do it is to let $x = a + bi$ and then solve for $a$ ...
2
votes
2answers
270 views

Fermat’s Little Theorem

I am struggling to spot how $\left(g^a\right)^\frac{p-1}{2}\equiv g^\frac{p-1}{2} (\mod{p})$ when $p$ is prime greater than $3$, $a$ is odd and $g$ is a primitive root modulo $p$. How does Fermat’s ...
11
votes
1answer
168 views

A proof involving the Euler phi function

Problem: Let $\varphi$ be the Euler phi function, where for any $n \in \mathbb{Z^+}$, $\varphi(n)$ is the number of positive integers less than $n$ that are relatively prime with $n$. ...
1
vote
2answers
26 views

Show $\sum_{1\leq n\leq x}\sum_{d\mid n}f(d)=\sum_{1\leq d\leq x}\sum_{1\leq m\leq x/d}f(d)$

I have been trying to get my head around this step in a proof, but havn't been able to, Question: Show $$\sum_{1\leq n\leq x}\sum_{d\mid n}f(d)=\sum_{1\leq d\leq x}\sum_{1\leq m\leq x/d}f(d)$$ ...
0
votes
1answer
20 views

Jacobians and ranks of a curve

I would like to know the following: How to find Jacobian and rank of an hyper elliptic curve like $x^5-x= y^2-y$? High regards Rosy
0
votes
0answers
15 views

Decryption of RSA

I am given the following information about an RSA-encryption: $e=31671865305320609$ (public key) and $n=10e+3$. Then I am given the ciphertext $c$ which I omit here due to his length. The task is to ...