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)

2
votes
1answer
322 views

Largest prime below a given number N

This came up as a part of algorithm puzzles: Given a number $N$, how to find the prime $P$ such that $P<N$ and the difference $N-P$ is minimum. For small $N$, simple sieves do work, but I'm unable ...
3
votes
2answers
170 views

A question about the Andrica's conjecture on the prime numbers

The Andrica's conjecture on the prime numbers states: given a couple of prime numbers $p_k$ and $p_{k+1}$ the following inequality holds: $$\sqrt{p_{k+1}}-\sqrt{p_{k}}\lt 1$$ Is it possible to show ...
1
vote
0answers
54 views

Equivalence class of quadratic forms

There is a natural action of the Hecke modular group (cf wiki) $\Gamma_0(q)$ on the set of integral quadratic forms $\phi = aX^2 + bXY + cY^2$ of discriminant $\Delta$ such that $a \equiv 0 \pmod q$. ...
10
votes
1answer
226 views

Is there any prime $p$ such that $(p-1)!+1=p^m$

According to Wilson Theorem, we know that $$p\mid(p-1)!+1$$ for $p\in\mathbb{P}$. Also, we have $(2-1)!+1=2^1\\ (3-1)!+1=3^1\\ (5-1)!+1=5^2$ I guess there is no such prime $p$ satisfying ...
2
votes
1answer
412 views

Computing $\bmod$s with large exponents by paper and pencil using Fermat's Little Theorem.

I'm having a bit of trouble computing $\bmod{mod}$s of large numbers using Fermat's Little Theorem. For example, how would you compute $7^{435627650}\mod 13$? The solution given is $435627650\mod ...
0
votes
1answer
55 views

Question regarding Legendre symbol and Quadratic reciprocity.

How would determine the value of the following Legendre symbol is $1$ or $-1$? $$\left(\frac{\frac{p - 1}{2}}{p}\right)$$ So far, I've been able to figure out this much: $$\left(\frac{p - ...
12
votes
1answer
414 views

Prove that $\sum\limits_{i=0}^{k} p^{2i}$ ($p$ is prime) is never a perfect square

Prove that $$ \sum_{i=0}^{k} p^{2i} $$ where $k > 0$ and $p$ is an arbitrary prime, is never a perfect square. I think you can prove it by letting $q = \sum\limits_{i=0}^k a_ip^i$, then expanding ...
3
votes
4answers
85 views

Solving for Modular arithmetic

Solve the equation $38z\equiv 21 \pmod {71}$ for z. Little confused by the questions. My attempt is: $38 \odot z = 21.$ Then find the inverse of 38 from mod 71 and multiply both sides. Lastly, take ...
6
votes
1answer
76 views

Function field question from Silverman's AEC

Just before Proposition 1.7 on page 5 of AEC (2nd ed), Silverman defines $M_P$ as an ideal in the affine coordinate ring. Then he states Proposition 1.7 (the intrinsic characterization of ...
4
votes
1answer
108 views

A numeral system built around Dirichlet series, by analogy of how positional numeral systems are built around power series?

For any natural number and chosen base p, the number admits a unique expression of the form $a_np^n + ... + a_2p^2 + a_1p^1 + a_0$, where $a_k < p$ for all k. This property is effectively what ...
0
votes
1answer
67 views

How prove this number $(a,b,n)=(1,1,4k)$

Let $a,b,n\in \mathbb{N}$, $\gcd(a,b)=1$, $\left(\sqrt{a}+i\sqrt{b}\right)^n\in \mathbb{R}$ Show that $(a,b,n)=(1,1,4k)$ or $(1,\sqrt{3},3k)$ or $(\sqrt{3},1,6k)$ where $k\in \mathbb{N}$, ...
12
votes
1answer
333 views

Irrational numbers, decimal representation

Can this even be proved? (Or disproved?) Any irrational number without a 0 (zero) in its decimal representation is transcendental. Not sure where to start on this one...
1
vote
1answer
79 views

Solve equations in a field with characteristic p.

Let $p$ be a prime and $K$ a field with characteristic $p$. How to solve the equation $x^2+2=0$ in the field $K$? Here $x, 2, 0 \in K$. Is it equivalent to solve the equation $x^2+2 = 0 \pmod p$? What ...
5
votes
1answer
139 views

Interesting phenomenon with the $\zeta(3)$ series

I noticed that if one takes certain partial sums of the series for $\zeta(3)$: $$\zeta(3) = \sum_{n=1}^{\infty} \frac{1}{n^3} \approx \sum_{n=1}^{N} \frac{1}{n^3}$$ an interesting phenomenon occurs ...
0
votes
1answer
67 views

Ring Isomorphism Proof

Let $p$ be a prime with $p \equiv 1 (\mod 4 )$. I am trying to show that $\mathbb{Z}[X]/(X^2 + 1, p) \cong \mathbb{Z}_p \times \mathbb{Z}_p$ is a ring isomorphism. I am not really sure how to ...
3
votes
2answers
54 views

Prove that $( \frac{l}{(l,m)},\frac{m}{(l,m)}) = 1$ [duplicate]

Prove that $( \frac{l}{(l,m)},\frac{m}{(l,m)}) = 1$, given that $l, m \in \Bbb{N}$. I had this question on my number theory final that I took earlier today. This was the second part of a 2 part ...
1
vote
2answers
91 views

Prove if $(l,m)=1$ and $l\mid mn$, then $l\mid n$.

I just took my number theory final and this was on the exam as the second question. It said to use the canonical decomposition of $l, m$ and $n$ for the proof. This is what I put down on the exam: ...
4
votes
1answer
58 views

Looking for help in understanding Jitsuro Nagura's analysis of the upper bound for $\psi(x)$

I'm working on understanding Nagura's analysis of the upper bound for $\psi(x)$ which is done in Lemma 2. I am unclear on one step of his reasoning. With Lemma 1, he establishes for $x \ge 2000$: ...
1
vote
0answers
296 views

Existence of Untouchable Betrothed Numbers

An untouchable number is a positive integer that cannot be expressed as the sum of all the proper divisors of any positive integer (including the untouchable number itself). The first few untouchable ...
1
vote
3answers
141 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 ...
4
votes
2answers
159 views

Direct product of polynomial rings

Let $n = pq$, where $p$ and $q$ are distinct primes. I am trying to show that: $$\mathbb{Z}_n[X] \cong \mathbb{Z}_p[X] \times \mathbb{Z}_q[X].$$ Would it suffice to say that $\rho(np) = ...
5
votes
1answer
135 views

analytic number theory, troubling bound on sum of $\varphi(n)$

I'm very confused about this bound, please give me any suggestions on how to prove it. (Note: $a \ll b$ is just a neater way to write $a = O(b)$) I am starting with the bound $$f(n) \ll ...
8
votes
3answers
296 views

Solve $x^3+x \equiv 1 \pmod p$

Find all the primes $p$ so that $$x^3+x \equiv 1 \pmod p \tag{1}$$ has integer solutions. We consider $x$ and $y$ are the same solutions iff $x\equiv y \pmod p.$ We can prove that $(1)$ cannot ...
0
votes
0answers
112 views

all various cubic extensions of Q7

I need to classify all various cubic extensions of $\mathbb Q_7$? How can one do it?
8
votes
1answer
283 views

$S$-Units notation and Dirichlet's unit theorem

I'm having a hard time understanding some notions of a paper I'm working on. Let $L/K$ be a finite normal extension of number fields and $S$ be a set of places of $K$ prime to $p$ where $p$ denotes an ...
0
votes
1answer
30 views

Make a partition that contains a set of points??

I am given a set of $M$ points in a segment (the edges are also points in this set) I would like to partition the segment (with equidistant points), in such a way that my partition contains all these ...
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
3answers
103 views

Definition of $b|a \implies 0|0$?

The definition I'm using for $b|a$ (taken from Elementary Numbery Theory by Jones & Jones): If $a,b \in \mathbb{Z}$ then $b$ divides $a$ if for some $q \in \mathbb{Z}$ $a = qb$. However, I ...
1
vote
1answer
99 views

finding a primitive root.

It says for part A to Find a primitive root r of 38? Im not sure if I did it right. I first calculated $\phi(38)=\phi(19*2)=18$. So there are 18 numbers that are relatively prime to 38. Listing them ...
24
votes
1answer
422 views

Series of Cyclotomic polynomials

How can I show that if $\Phi$ is a Cyclotomic polynomial, $$\Phi_n(x)=\prod_{\substack{1\leq k\leq n\\(n,k)=1}}(x-\zeta_n^k)$$ With $\frac{d}{dx}\Phi_n(x)=\Phi'_n(x)$ Then, ...
3
votes
1answer
62 views

Primitve roots and congruences?

Let $p$ be an odd prime. Show that the congruence $x^4$$\equiv -1\text{ (mod }p\text{)}\ $ has a solution if and only if $p$ is of the form $8k+1$. Here is what I did Suppose that $x^4$$\equiv ...
2
votes
1answer
91 views

Solving the equation for $x$ in $Z_n$

How do you solve for x in the the $Z_n$ specified? For example, for the equation: 1) $3\odot x\oplus8\equiv1(\rm{mod} 10)$ or 2) $342\odot x\oplus 448\equiv73(\rm{mod}1003)$ How would you solve for ...
7
votes
1answer
235 views

(USAJMO)Find the integer solutions:$ab^5+3=x^3,a^5b+3=y^3$

Find the integer solutions: $$a·b^5+3=x^3,a^5·b+3=y^3$$ This is the first problem of today's USAJMO (has finished),I only find a trival result that $x\equiv y \pmod6$ and $abxy≠0 \pmod 3$. Thanks in ...
5
votes
1answer
350 views

Is this number theory conjecture known to be true?

I've been working on proving that there is always a prime between $n$ and $2n$, and also that there is always a prime between $n^2$ and $(n+1)^2$ (Legendre's conjecture). I believe I've proven those ...
7
votes
3answers
174 views

Finding a prime number between $n$ and $2n$

I am trying to find a prime number between $n$ and $2n$. I know that the number of primes between $n$ and $2n$ is $n/(2\ln n)$. I was thinking of choosing a random number between $n$ and $2n$ and ...
2
votes
1answer
63 views

number theory Diophantine equation

I need help understanding an old homework question. It said to find all the solutions $$x^2 + y^2 = 3z^2 + 3t^2$$ My professor said for $x^2 + y^2 >0$ the LHS is divisible to 3 to an even power ...
1
vote
2answers
173 views

Determine number of squares in progressively decreasing size that can be carved out of a rectangle

How many squares in progressively decreasing size can be created from a rectangle of dimension $a\;X\;b$ For example, consider a rectangle of dimension $3\;X\;8$ As you can see, the biggest square ...
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 ...
3
votes
1answer
97 views

Orbits of the $\operatorname{Aut} (G)$ for $G = (\mathbb Z/m\mathbb Z) ^k$

$\operatorname{Aut}(G)$ turns out to be group of invertible $k\times k$ matrices over $\mathbb Z/m\mathbb Z$. It turns out that the problem is equivalent to seeing whether a $k$ vector with entries ...
2
votes
1answer
100 views

how to show associativity of multiplication for not just 3 operands but for n operands

ie Id like to show a(bc)=(ab)c but for any n operands eg abcdefg=gfdcabe etc I can see this is very intuitive that this should be true for all n operands, but as a logical exercise I would like to ...
16
votes
5answers
1k views

Intervals that are free of primes

How can I prove that exists intervals as large as I want that are free of primes? I mean, $\forall \ k \in \mathbb{N}, \exists \ k$ consecutive positive integers none of which is a prime.
4
votes
0answers
113 views

Characterization of quadratic polynomials over $\mathbb{Z}/p\mathbb{Z}$

This is a nice question which I'd like to share with everyone. Let $f:\mathbb{Z}/p\mathbb{Z} \to \mathbb{Z}/p\mathbb{Z}$ be a function s.t. for each $a \in (\mathbb{Z}/p\mathbb{Z})^{\times},$ the ...
1
vote
2answers
1k views

Solving Linear Congruence Equation: Finding the Nonnegative Integer Representation

I have a question for a part of the following problem: Solve the linear congruence 7x ≡ 6(mod 29) I understand how to find the linear combination equality using ...
2
votes
4answers
102 views

How do I show that $6(4^n-1)$ is a multiple of $9$ for all $n\in \mathbb{N}$?

How do I show that $6(4^n-1)$ is a multiple of $9$ for all $n\in \mathbb{N}$? I'm not so keen on divisibility tricks. Any help is appreciated.
1
vote
1answer
48 views

How to concisely prove that if a is bigger than one, then $(a \mid (b \mod a+c \mod a)) \equiv a \mid b+c$.

Show that if $a \in \mathbb{Z_{\geq 0}}$, then the following proposition holds: $a \mid [b {\pmod{a}}+c \pmod {a}] \iff a \mid b+c$. I've been trying to prove it, but I am blocked. I tried using ...
0
votes
1answer
52 views

Transcendental numbers and spigot formulae

I thought that one property of transcendental numbers is that to know, say, the millionth decimal digit, you had to know the previous 999,999. Looks like (with e.g. the BBP formula) I'm wrong, that ...
0
votes
1answer
42 views

Is the “least non-negative residue” of $b^p \pmod{m}$ just $b^p \pmod{m}$?

I'm just wondering if the "least non-negative residue" of $b^p \pmod{m}$ is just $b^p \pmod{m}$ itself. What is the "least non-negative residue"? How is it found? Is this how it is found? Just by ...
3
votes
1answer
105 views

Why don't I end up with the same splitting field?

I've understood that the splitting field of $x^4+2$ and the splitting field of $x^4-2$ over $\mathbb{Q}$ are both the field $\mathbb{Q}(\sqrt[4]{2} , i)$. With degree $8$ over $\mathbb{Q}$. This ...
-2
votes
1answer
110 views

Modular Arithmetic: Least Non-negative Residues

I am to compute the least non-negative residue of $4^n \pmod{9}$ for $n = 1, 2, 3, 4, 5, \dots$ I must also prove that $6 · 4^n ≡ 6 \pmod{9}$ for every $n > 0$.
0
votes
4answers
168 views

Calculations by Hand

Find the least non-negative residue of: (i) $5^{18}$ mod $11$ (ii) $68^{105}$ mod $7$ (iii) $4^{47}$ mod $12$ (iv) $66^{75}$ mod $19$ C++ code failed... I'm trying to do by hand now. Maple has ...