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)

4
votes
1answer
35 views

Does there exist a general technique for solving systems of multivariable linear congruences

I'm aware for coprime moduli we have the CRT for solving the problem $$ \begin{matrix} a_0 x \equiv b_0 \mod m_0 \\ a_1 x \equiv b_1 \mod m_1 \\ \vdots \\ a_n x \equiv b_n \mod m_n \end{matrix} $$ ...
0
votes
1answer
36 views

I need help with the powers of an integer, modulo m

I am currently reading a chapter in math textbook about the powers of an integer, modulo m. I am having troubles with the following claims Suppose that $a^r \equiv a^s(mod\text{ } m)$, where $r>s$...
6
votes
2answers
149 views

Question on the coefficients of $(1+x+x^2+x^3+x^4)^{496}$

Consider the expansion $$(1+x+x^2+x^3+x^4)^{496} = a_0+a_1x+\cdots+a_{1984}x^{1984}.$$ $\quad$ (a) Determine the greatest common divisor of the coefficients $a_3,a_8,a_{13},\ldots,a_{1983}$. $\...
5
votes
2answers
74 views

Rational numbers as vectors in infinite dimensional space with the basis $( \log 2,\log 3, \log 5, \log 7, \dots, \log p, \dots) $

Since every natural number can be represented as $a=2^{n_1}3^{n_2}5^{n_3}7^{n_4}\cdots p_k^{n_k}\cdots$ it makes sense to represent natural numbers by vectors, using the properties of logarithms: $$\...
0
votes
1answer
19 views

Number of positive divisors between $a$ and $a^2$

Let $a$ be a positive integer and let $M(a,a^2)$ denote the number of positive divisors of $a^2$ between $a$ and $a^2$, not including $a$. Prove that $M(a,a^2) = \dfrac{\tau(a^2)-1}{2}$ where $\tau(n)$...
12
votes
1answer
174 views

Prove that $(2^n-1)(3^n-1)$ is not a perfect square

Prove that $(2^n-1)(3^n-1)$ is not a perfect square. I have tried this problem for a few days already and I feel I am really far from solving it. Most of my approaches have been analyzing how many ...
10
votes
3answers
59 views

Calculate the number of integers in a given interval that are coprime to a given integer

We can calculate the number of integers between $1$ and a given integer n that are relatively prime to n, using Euler function: Let $p_1^{\varepsilon1}\cdot p_2^{\varepsilon2} \cdots p_k^{\varepsilon ...
9
votes
0answers
91 views

For any $x\in \mathbb{N}$ does there exist $m\in \mathbb{N}$ such that $2x+1+2m, 2x+1+4m$ are both prime?

Could someone please give me a proof (or counter example) for this (I believe it is true): For any $x$ (Whole Number) there exists some $m$ (Also Whole) such that $2x+1+2m$ and $2x+1+4m$ are both ...
4
votes
2answers
37 views

Ring of algebraic integers as lattice points in the complex plane

Let, $i=\sqrt{-1}$ and $\omega = e^{\frac{2\pi i}{3}}$. I know that we can represent the ring of integers $\mathbb{Z}[i]$ and $\mathbb{Z}[\omega]$ as square and triangular lattice on complex plane ...
-3
votes
4answers
51 views

If $\gcd(a,3)=1$, then $a^3\equiv \pm 1\pmod 9$ [closed]

Show that if $\gcd(a,3)=1$, then $a^3\equiv \pm 1\pmod 9$ (which is equivalent to $9 \mid a^3\pm 1$, I guess). Also, show that the equation $3x^2+5=2y^3$ will have no solutions.
5
votes
1answer
96 views

1-1 correspondence of class group of an order '$\mathcal{O}$' and elliptic curves having complex multiplication by $\mathcal{O}$

I came across these two results Let $\mathcal{O}$ be an order in an imaginary quadratic field.There is a 1−1 correspondence between the ideal class group $C(\mathcal{O})$ and the homo-thety classes ...
1
vote
1answer
23 views

I need an explanation about the following unbounded function

Consider the set $E=\{2n:n=1,2,3..\}$. The set E is not paricularly sparse in N-every other integer belongs to E and this regularity is reflected in the size of the sum $$S_E(N)= \sum_{m \in E, m \...
0
votes
2answers
25 views

Frequency of relatively prime pairs in all pairs

What would be the probability of getting a relatively prime pair if we pick two random numbers in natural number set? What if we pick more than two number?
0
votes
1answer
37 views

Can we build two towers of equal height, having $n$ cubes with edges $1,2,3,\dots,n$ centimetres respectively?

This is a problem i found on number theory and i'm having trouble with. The following is my attempt to solve it. We want $n$ cubes, that will make up two towers of volume $V$ and height $h$. I ...
1
vote
0answers
19 views

Upper Bound for discrete objective value

I really need your help with the following problem: Let $ N \ge 3 $ be given, then consider $$ L(N)=\max\left\lbrace \sum_{j=2}^{N-1} \frac{c_j}{j} \, \middle| \, c_j \in \mathbb{N}, \nexists 0\le d \...
0
votes
0answers
174 views

I've some results in Number Theory, but I don't know if they're already discovered, what should I do with them?

I checked the net but didn't find anything similar. If $x^3+y^3+z^3$ is divisible by $k$ but not $k^2$, $x^n+y^n+z^n$ is divisible by $k$. $n$ belongs to natural numbers, $k$ can only be $2$ or $3$. ...
0
votes
2answers
34 views

Sum of two relatively prime squares in two distinct ways

I hope that this isn't simple because I've been scratching my head with it: In David Burton's "Elementary Number Theory", there is a question that says that in 1647, Mersenne noted that when a number ...
0
votes
0answers
12 views

Integers in base $b$ equal to the sum of the squares of their digits

Give a complete list of all integers not exceeding $50$ that, relative to some base $b$, are equal to the sum of the squares of their digits. We need $a_1b+a_0 = a_1^2+a_0^2$. I tried turning this ...
5
votes
2answers
94 views

If $f$ has more than one root in $K$, then $f$ splits and $K/k$ is Galois?

Let $f \in k[x]$ be an irreducible polynomial of prime degree $p$ such that $K \cong k[x]/f(x)$ is a separable extension. How do I see that if $f$ has more than one root in $K$, then $f$ splits and $K/...
1
vote
1answer
39 views

Which of the numbers has the largest number of divisors?

Which of the numbers $1,2,\ldots,1983$ has the largest number of divisors? Firstly notice that each number less than or equal to $1983$ has at most $4$ different prime divisors since $2 \cdot 3 \...
1
vote
1answer
52 views

Number of divisors greater than a number [closed]

Given a number $x$, it is easy to count its total number of divisors by combinatorial method. Is there a way to efficiently determine the number of divisors of $x$ greater than a given number $y$?
1
vote
1answer
19 views

Normal closure of a number field and a possible quadratic field in it

While reading about prime decomposition in number fields, I came across following statement (stated as a fact): Let $K$ be a number field and $d= \text{disc}(\mathcal{O}_K)$, then the normal ...
9
votes
3answers
147 views

Summation with combinations

Prove that $n$ divides $$\sum_{d \mid \gcd(n,k)} \mu(d) \binom{n/d}{k/d}$$ for every natural number $n$ and for every $k$ where $1 \leq k \leq n.$ Note: $\mu(n)$ denotes the Möbius function. I have ...
-3
votes
1answer
35 views

Question on number theory [closed]

If a²+(5/2)b²+c²= 2ab+bc+ca then a+2b+2c equals what? I am unable to think how to solve it.. Please help
0
votes
1answer
47 views

Following the previous question: Existence of the natural density …

Following the previous question: Let $A=\{a_n\}$ is a strictly-increasing sequence of positive integer. The natural density of this sequence is defined by $\delta(A)=\lim_{n\rightarrow \infty} \frac{...
1
vote
1answer
41 views

Splitting of primes in real cyclotomic field

The question is from Marcus' book, "Number Fields" (exercise 12, Chapter 4) Let $\omega= e^{\frac{2\pi i}{m}}$ and $p$ be a rational prime not dividing $m$. Then how does $p$ split in $\mathbb{...
2
votes
2answers
55 views

Number of even numbers having digit 2 in them.

I am trying to count numbers from 1 to N which exist in A121022 but I am unable to think of solving in better than O(NLog(N)) , can you suggest a better algorithm?
1
vote
1answer
35 views

Some questions on Euler's phi function

I was reading Number Theory by George E. Andrews (Dover 1994,) problem set 6-1, p. 81. (I'm not a student; I just find problems like these entertaining like some people enjoy crosswords or Sudoku.) ...
0
votes
2answers
57 views

Can an irrational number be expressed as a sum of other irrational numbers, at least one of which is not an integral multiple of the required number?

For example, $\pi = Ae + B\sqrt 2+ \cdots$ ($A,B,\ldots\in\mathbb R$) (Equations like "$\pi = 3\pi - 2\pi$" are not allowed.)
4
votes
2answers
78 views

How can we create arbitrarily long instances of the Euclidean algorithm?

How can we create arbitrarily long instances of the Euclidean algorithm? What kind of numbers are useful? What is the relationship between the size of these numbers and the number of steps?
11
votes
6answers
2k views

Why does the Euclidean algorithm always terminate?

Why does the Euclidean algorithm always terminate? Can we make this effective by bounding the number of steps it takes in terms of the original integers?
9
votes
1answer
134 views

Is $n^7 - 77$ ever a Fibonacci number?

As the question title suggests, is $n^7 - 77$ ever a Fibonacci number, where $n$ is a integer?
0
votes
1answer
47 views

Given the value of a polynomial mod $611953$, find $x$?

Given a polynomial of degree $n$, and a value $\pmod{611953}$, find the possible $x$ at which this value occurs? For example a polynomial $p(x)$ is given of some degree $n$, and a number is given ...
2
votes
0answers
28 views

How to do this integral? $\int_{-i\infty}^{i\infty}F_{\psi}(z) dz$?

Let $\psi$ be a character with conductor $f_\psi$. Define $$F_\psi(z)=\begin{cases}\sum_{n=1}^{\infty}\psi(n)e^{2\pi i nz}&\text{ if }& \text{Im}(z)>0\\ -\sum_{n=1}^{\infty}\psi(-n)e^{-2 \...
1
vote
4answers
83 views

Does $18^{247}$ divide (500!)?

I wanted to find the highest power of 18 that divides 500! I did this : $18=6*3=(2*3)*3$ For 2, highest power is 494 For 3, highest power is 247, Therefore highest power of 6 is min{494, 247}...
3
votes
1answer
28 views

Factorization of primes in normal closure of Quartic Field

Motivation for the question comes from Marcus' book on Number Fields (exercise 13, Chapter 4). Let $K= \mathbb{Q}[\sqrt[4]{m}, i]$ where $i=\sqrt{-1}$, $m\in \mathbb{Z}$ and $m$ is not a square. ...
1
vote
1answer
72 views

How to factorize a number into prime numbers

I have to compute the Legendre symbol $4307 \choose 7549$, so I have to factorize $4307$ into prime numbers. Is there any mathematical shortcut to do it?
0
votes
0answers
24 views

Is it conjectured there infinitely primes $p$ such that M($p$) is a Mersenne Prime, where p is of an arithmetic progression?

Are there infinitely many primes $p$ of the form $an+d$ for fixed $a$ and $d$ coprime, and that $2^p-1$ is also prime? In other words, there are infinitely many primes $p$ $=$ $a$ $\pmod d$ ($a$ and ...
1
vote
2answers
101 views

How to read a proof? [closed]

As I go deeper and deeper into upper division math courses, I find some proofs to be very challenging to understand. Right now I am trying to understand Gauss's lemma in number theory and I can't ...
0
votes
1answer
27 views

Computing the Legendre symbol $6 \choose 11 $

Compute the Legendre symbol $6 \choose 11$ By euler's critetion, ${6 \choose 11}=-1$, but ${6 \choose 11}={3 \choose 11 }{2\choose 11}=-1*-1=1$. I am confused about that result.
0
votes
1answer
43 views

What is the equivalent statement of GRH in term of Redheffer Matrix or Farey Sequences?

We all know that Riemann Hypothesis (RH) has many equivalent statements. There is one statement which expresses RH in term of Redheffer matrix, there is another equivalent statement of RH which ...
0
votes
0answers
13 views

Effective estimates for k-almost primes

Given an integers $k$ and $\ell$ and a real numbers $\varepsilon>0$, define $f(k,\ell,\varepsilon)$ as the least $x_0$ such that for all $x>x_0$ the fraction of $\ell-$rough numbers up to $x$ ...
2
votes
4answers
70 views

Decreasing sequence numbers with first digit $9$

Find the sum of all positive integers whose digits (in base ten) form a strictly decreasing sequence with first digit $9$. The method I thought of for solving this was very computational and it ...
3
votes
2answers
102 views

In abstract algebra, what is an intuitive explanation for a field?

Wikipedia has the following to say about fields. In mathematics, a field is one of the fundamental algebraic structures used in abstract algebra. It is a nonzero commutative division ring, or ...
4
votes
1answer
45 views

Abuse of notation for infimum and supremum

I would like to take the infimum and supremum of two sets $(\frac{1}{2} e^{8m+4} - 1, e^{8m+4} - 1)$ and $(\frac{1}{2} e^{8m+4}, \frac{3}{2}e^{8m+4})$, but writing $\sup((\frac{1}{2} e^{8m+4}, \...
9
votes
0answers
50 views

What to keep in mind when attempting proof of basic properties of divisibility/what techniques are useful/what's the intuition for showing them?

So I am currently trying to prove some basic divsiibility relations, as follows. If $a \mid b$ and $a \mid c$, then $a \mid (b + c)$. If $a \mid b$ and $s \in \mathbb{Z}$, then $a \mid sb$. ...
2
votes
1answer
26 views

ceiling of an expression

If we need to find the ceiling of this expression (A-11)/100 then is it correct to simply write the above expression as ...
1
vote
3answers
71 views

Product of the first $n$ Fibonacci numbers is a perfect square

Suppose that $F_{n+2}=F_n+F_{n+1}$ and $F_1=F_2=1$. Can the number $P_n=F_1\cdots F_n$ be a perfect square if $n\ge 3$?
0
votes
2answers
29 views

Prove that If $m'$ is a common multiple of $s$ and $t$, then $m | m'$. Here $m$ is the LCM of $s$ and $t$.

Prove that If $m'$ is a common multiple of $s$ and $t$, then $m | m'$. Here $m$ is the LCM of $s$ and $t$. Although the statement is intuitively clear to me I don't know how to prove.
4
votes
1answer
57 views

n-th roots of unity summing to $0$

Let $\zeta = e^{2\pi i/n}$ be an $n$-th root of unity, and let $S = \{\zeta^m|m=0,1,\ldots,n-1\}$ be the corresponding sets of all $n$-th roots of unity. Let $k \leq z$. Let $C \subseteq S$ such ...