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

Prove that there are infinitely many composite numbers of the form $2^{2^n}+3$.

There are infinitely many composite numbers of the form $2^{2^n}+3$. [Hint: Use the fact that $2^{2n}=3k+1$ for some $k$ to establish that $7\mid2^{2^{2n+1}}+3$.] If $p$ is a prime divisor of ...
0
votes
1answer
33 views

Wieferich prime-Lang-Trotter conjecture connection?

Crandall-Dilcher-Pomerance prediction states that the number of Wieferich primes $<x$ is $log\ logx $ N.Katz in "WIEFERICH PAST AND FUTURE" states; The Crandall-Dilcher-Pomerance prediction is ...
4
votes
4answers
94 views

Wrapping my head around different base-number systems

this is my first post on this forum, I'm interested in mathematics but don't have any education beyond the high-school level in the subject, so go easy on me. What I know right now: the base-10 ...
2
votes
0answers
28 views

Order of Magnitude

It is well known (see here, for example) that we have $$ \psi\left(\frac{1}{2},T\right)=\sum_{p\leq T}\frac{1}{p}=\log(\log T)+A+O\left(\frac{1}{\log T}\right), $$ where $\psi(\sigma,T)=\sum_{p\leq ...
2
votes
2answers
54 views

If $a \in \mathbb{I}$ , how is $\overline{\mathbb{Z}+ a\mathbb{Z}}=\mathbb{R}$

If $a \in \mathbb{I}$ , how is $$\overline{\mathbb{Z}+ a\mathbb{Z}}=\mathbb{R}$$ It says in my notebook that this set in dense in $\mathbb{R}.$ How do I prove this density? With say $\mathbb{Q}$ and ...
0
votes
0answers
18 views

ElGamal signature for finding the private key

Alice uses an ElGamal signature with base the group $Z^*_{107}$ and parameter $g=3$ of order $q=53$.The private key of Alice is some $x \in \{0,1,.....,52\}$ and the public key of her is $y=10$.To ...
1
vote
1answer
44 views

In the definition of Carmichael number, why is it necessary to have $(b, n) = 1$?

In number theory, a Carmichael number is a composite number $n$ which satisfies the modular arithmetic congruence relation $$b^{n-1}\equiv 1\pmod{n}$$ for all integers $1<b<n$ which are ...
0
votes
1answer
55 views

Can a Carmichael number be even?

Can a Carmichael number be even? I know that a Carmichael number is a positive composite integer $n$ such that $a^n\equiv a \pmod n$ for all integer $a$. So what does I need to prove or disprove ...
0
votes
1answer
19 views

Combinatoric for number of ways to have monotone-increasing sequence

I hope I am using the right term. By monotone-increasing I mean to imply that it is a non-decreasing sequence. So for example a sequence $1, 1, 2, 5, 6, 10, 10, 11$, etc. Anyhow, consider a ...
4
votes
0answers
46 views

Find all integers $a,b,c$ [duplicate]

This question comes from the 2007 IMO shortlist: Find all integers $a,b,c$ such that $ab-c$, $bc-a$ and $ca-b$ are powers of two (of the form $2^k$ where $k \geq0$). What are some methods of ...
-2
votes
1answer
23 views

Rabin-Miller compositeness

Find a witness Rabin-Miller of compositeness of $n=25$ Can anyone explain and show me a way on how to solve this question?and generally how to find witness Rabin-Miller
2
votes
2answers
110 views

Frog jumping on leaves

$N$ leaves are arranged round a circle. A frog is sitting on first leaf and starts jumping every $K$ leaves. How many leaves can be reached by a frog?
0
votes
1answer
46 views

Diophantine equation - Special form (quadratic)

I am dealing with a series of quadratic diophantine equations that all have the same form: $$A^2x^2 - C^2y^2 + Dx - Ey + F = 0$$ ($A,C,D,E >0$ | $A$ and $C$ have a common factor (or $C=1$) | ...
0
votes
0answers
27 views

Proof for sum of divisor of a given range

Question is like this: We are given a number "n"(n<=10^7) and we have to calculate G(n) which is G(n)=F(1)+F(2)+F(3)+F(4)+....F(n). where F(x) is the sum ...
-2
votes
1answer
27 views

For all $n>2$, $\mu(1!)+\mu(2!)+\cdots+\mu(n!)=1$ [closed]

Show that for all $n>2$, $$\mu(1!)+\mu(2!)+\cdots+\mu(n!)=1$$ Here $\mu$ is the Mobius function.
4
votes
1answer
31 views

Unramified Hecke character

I'm looking for a reality check here: Let $\chi$ be a character of $(F^\times\backslash \mathbb A_F^\times)^1$ where $F$ is a number field. Call $\chi$ unramified at a place $v$ if ...
0
votes
1answer
17 views

Big-O Notation & Legendre Symbol

Why the following equality is true if we let N to infinity; $\sum _{m>\sqrt{N}}\frac{1}{m}(\frac{d}{m}) = O(\sqrt{\frac{1}{N}})$ , where $(\frac{d}{m})$ is Jacobi Symbol.
0
votes
0answers
27 views

Number of Representations

In the text book the formula is given that; $R(n) = w\sum _{m\mid n}(\frac{d}{m})$ where $w$ is the number of the automorphs when $d<0$ and $1$ if $d>0$ and where $d$ is the discriminant of the ...
4
votes
0answers
70 views

Exponential diophantine equation: $2p^2-6p+7=3^n$.

I'm trying to prove that the only integer positive solutions are $(n=1,\ p=1)$ and $(n=3,\ p=5)$. Is there a simple way to do that?
2
votes
1answer
56 views

ABC conjecture consequence

At page 6 of the book: "Prime Numbers The most mysterious figures in Math" this statement is listed as one of the consequences of the ABC conjecture: There are Infinitely many Wieferich primes. This ...
0
votes
1answer
27 views

How prove that for each $x\in S$ there exist $m\leq [\frac{n+1}{4}]$ such thst $f(f(…f(x)…))=x$?

For a given integer $n$ , let $S$ be a set of all odd natural numbers less than or equal to $n$ and relatively prime to $n$. For $x\in S$ define $f(x)$ to be the greatest odd divisor of $n-x$. Prove ...
5
votes
0answers
71 views

Neukirch's motivation for $p$-adic numbers

I've started reading Neukirch's Algebraic Number Theory book and at the beginning of Chapter II he starts his motivation for the $p$-adic numbers as follows: "The idea originated from the observation ...
0
votes
3answers
57 views

The square of n+1-th prime is less than the product of the first n primes.

I wanted to prove the following question in an elementary way not using Bertrand postulate or analytic estimates like $x/\log x$. The question is $$ p_{n+1}^2<p_1p_2\cdots p_n,\qquad(n\geq4) $$ I ...
0
votes
2answers
24 views

number theory closure property

Consider the set of all numbers less than $n$ and relatively prime to it. Let $S = \{a_1,a_2,...,a_{φ(n)}\}$ be this set. How to prove that if $a \in S$ and $b \in S$, then $ab \pmod n \in S$.
3
votes
4answers
104 views

Find the smallest positive integer that ends in $17$, is divisible by $17$, and the sum of its digits is equal to $17$.

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with primes and composities but other than that, the textbook gave no hints ...
3
votes
1answer
44 views

Finding period of a recursive sequence defined by modular operator?

If $f(x)$ is defined as : $f(x)=i$ ,if $x\equiv i$ (mod n), $0\leq i< n$ How can I prove whether the following recursive sequences are periodic or not? ...
6
votes
0answers
94 views

How prove that for a given integer $k$ there exist infinitely many $n$ such that $S(2^n+n)+k<S(2^n)$?

Let $S(n)$ be the sum of digits of $n$. How prove that for a given integer $k$ there exist infinitely many $n$ such that $S(2^n+n)+k<S(2^n)$? I have modified this problem: Denote by $S(a)$ the ...
1
vote
0answers
30 views

Complex integration over a simple pole

A paper I am reading addresses the following integral: $$\int^\infty_{-\infty}\frac{F'}{F}(1+it)h(t)dt$$ where $F$ is a function of $s\in\mathbb C$ with a simple pole at $s=1$, and $h$ is a smooth, ...
2
votes
2answers
80 views

From a silly (long division) puzzle comes an interesting number-theory “theorem” (quotes indicate some doubt).

I've worked a BUNCH of this type of long division puzzle. EDIT (The problem represents LOELPE/MNTN where EP is the quotient and LEAC is the remainder, with LIONP representing E times MNTN, PPMC ...
0
votes
1answer
64 views

Recurrence relation: $c_{k+1}=c_k+\frac{1}{(k+1)!}$

I have no idea how to proceed solving a recurrence relation like this. I know that the terms approach $e$ but beyond that I have no idea. The relation is$$c_{k+1}=c_k+\frac{1}{(k+1)!} \ \ ; \ c_0=1$$ ...
3
votes
2answers
87 views

How to replace addition with multiplication to find the next integer value?

Sorry in advance for my lack of mathematical knowledge, I am very new to it. Yesterday, I posed this question to myself: "In a world without addition or subtraction, how could we derive the next ...
6
votes
2answers
188 views

Find the number of sets of $(a,b,c)$ for $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=\frac{29}{72}$

If $\dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c}=\dfrac{29}{72},\ \ c<b<a<60,\ \ \{a,b,c\}\in\mathbb{N} $. How many sets of $(a,b,c)$ exists ? Options $a.)\ 3 \quad \quad \quad \quad ...
0
votes
1answer
26 views

Quadratic Forms with Positive Discriminant

I have some difficulties on the concept of "Quadratic Forms", I want to explore my knowledge about this topic, but except a few documents I couldn't find much documents, My question is simply about ...
0
votes
1answer
21 views

Fermat's numbers as the difference of two consecutive squares

By well known result we know that Fermat's number is prime if and only if it can be uniquely written in the sum of two squares. My question is that: Can we write every Fermat's number as the ...
0
votes
1answer
31 views

Composite Fermat's numbers

We know that Fermat's numbers are $F_n= 2^{2^n} +1$. My question is: does there exist certain forms of $n$ for which $F_n$ is always composite?
0
votes
0answers
32 views

Sum of inverse of Fermat's numbers

What is the sum of inverse of all Fermat's numbers? I know the series is convergent using comparison by geometric series with common ratio 1/2 and first term 1/2 but I don't know how to find the sum?
1
vote
0answers
24 views

Why are rational numbers required in cusps of congruence subgroups?

While we consider the action of congruence subgroups on $\mathbb{H}$ (the upper half plane), we compactify using an additional point at infinity, that is fine. But why do we add even all rational ...
0
votes
4answers
52 views

determining which cyclotomic polynomial is $x^8 -x^4+1$

Given that the following polynomial\begin{equation*}f(x)=x^8-x^4+1\end{equation*} is a cyclotomic polynomial $\Phi_n$ for some $n\in \mathbb N$. are there some basic tools to determine $n$? I know ...
5
votes
3answers
43 views

Proof question: Prove that 2^(odd integer) + 5^(odd integer) + 2 is a multiple of 3, and 4^(any integer) + 1 can be expressed as 5n, 5n + 1 or 5n + 2.

I had been working on the claim in the above question for sometime now. Statistically speaking, it works. For example: $$\left(2^1 \right)+\left(5^1\right)+2=9,\\ ...
36
votes
3answers
602 views
+200

Prove that there exist infinitely many integers $(n^{2015}+1)\mid n!$

I conjecture that there exist infinitely many integers $n$ such that $$(n^{2015}+1)\mid n!.$$ I have seen a simpler problem that there exist infinitely many integers $n$ such that $(n^2+1)\mid ...
3
votes
0answers
61 views

Find a real number with even digits in a given base

A real number x ∈ (0,1) is called b-good if x converted to any base b >= 2 has all digits ...
4
votes
2answers
61 views

Find the value of $2xy$ .

If $13x+17y=643$ ,$\{x,y\}\in \mathbb{N}$, then what is the value of two times the product of $x$ and $y$ ? Options $a.)\ 744\quad \quad \quad \quad \quad b.)\ 844\\ \color{green}{c.)\ ...
5
votes
1answer
44 views

Prove that there exist infinite many integers $m$ such that $\gcd\left(\binom{m}{k},l\right)=1$

Let $k,l$ be two given integers. Prove that there exist infinite many integers $m(\ge k)$ such that $$\gcd\left(\binom{m}{k},l\right)=1$$ The number-theory book hint use Lucas' theorem,I can't How to ...
1
vote
1answer
29 views

Equivalence of different prime factorizations in $\mathbb{Z}[\zeta_3]$

I'm reading that in the ring $\mathbb{Z}[\zeta_3]$, where $\zeta_3$ is the cubic root of unity, two prime factorizations of $4 = 2 \times 2 = (1 + \sqrt{-3})(1 - \sqrt{-3})$ are equivalent, because up ...
2
votes
0answers
32 views

rates of relatively prime numbers

Given a positive integer $n $ and a real number $1\ge r >0$, we can define two numbers on counting relatively prime numbers: $\alpha_r^n :=|\{m\in\mathbb {Z}_+|0 <m \le nr, (m,n)=1\}| $ ...
0
votes
1answer
29 views

Sum involving the Möbius function

I have two multiplicative functions $f$ and $g$ and the expression $$\sum_{d\mid n} \mu(d) f(d)g(n/d).$$ In case $f=1$ this is just the Möbius inversion. But what can we say about it in this more ...
3
votes
1answer
56 views

Does $(a^p + b^p)^{p-1} \equiv 1 \pmod {p^2}$ have any solutions where $a$ and $b$ are co-primes less than $p$?

How will you prove that $(a^p + b^p)^{p-1} \equiv 1 \pmod {p^2}$ has no solution where $p$ is a prime number and $a$, $b$ are two co-primes less than $p$? If this equation has a solution, then what it ...
1
vote
0answers
26 views

Why only congruence subgroups for modular forms?

When we define modular forms, why do we restrict ourselves to congrumence subgroups? Why not any subgroup of finite index? Or, even more generally why not any subgroup? Is it just a matter of ...
0
votes
0answers
29 views

Does this suggest a unique additive factorization on the rational numbers?

I'm reading Hardy's Course of Pure Mathematics (3rd edition) and there is an interesting exercise on page 34: Any positive rational number can be expressed in one and only one way in the form ...
0
votes
2answers
71 views

The number $2^{2^n} + 2^{2^{n - 1}} + 1$ can be expressed as the product of at least $n$ prime factors

Prove that the number $2^{2^n} + 2^{2^{n - 1}} + 1$ can be expressed as the product of at least $n$ prime factors, not necessarily distinct. Doing what the hint has suggested, I have done the ...