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)

3
votes
1answer
52 views

Find pairs $(a,b)$ with $\gcd(a,b),\gcd(a + 1, b),\ldots, \gcd(a + k, b)$ given

Given a set of GCD's, how to find a set of numbers that satisfy all their criteria? Suppose we are given a $k$ integers $\gcd(a,b),\gcd(a + 1, b),\ldots, \gcd(a + k, b)$ for some k. How to get a and b ...
1
vote
1answer
22 views

Endomorphism ring of an abelian variety and its reduction mod $\mathfrak{p}$

Let $A$ be an abelian variety defined over a number field $K$. Let $\mathfrak{p}$ be a prime of $K$ for which $A$ has good reduction and let $k=\mathcal{O}_{K,\mathfrak{p}}/\mathfrak{p}$. Let $\...
0
votes
3answers
101 views

Find all N in $\phi(N)=98$ [closed]

Solve the equation $\phi(N)=98$ I have no idea how to do it. How to find all N?
-1
votes
0answers
20 views

Mandelbrot set and times tables

I recently saw a mathologer video on YouTube titled Times tables, Mandelbrot set and the heart of mathematics. It was about generating patterns using tables of numbers. I don't have any idea about it. ...
2
votes
0answers
47 views

Proof about fibonacci numbers by induction

Let $u_1,u_2,....$ be the fibonacci sequence. a) Prove by induction or otherwise thar for n>0, $$u_{n-1}+u_{n-3}+u_{n-5}+...<u_n$$ the sum on the left continuing so long as the subscript remains ...
3
votes
3answers
84 views

Problem about number representations

To multiply two numbers, such as 37 and 22, set up a table according to the following pattern. \begin{array}{|c|c|} \hline 37&22 \\ \hline 18&44 \\ \hline 9&88 \\ \hline 4&176 ...
2
votes
1answer
80 views

$\phi(a_1),\phi(a_2),\ldots$ forms an increasing arithmetic sequence?

Let $\phi(m)$ denote the totient of $m$. Does there exist an infinite sequence of positive integers $a_1,a_2,\ldots$ such that $\phi(a_1),\phi(a_2),\ldots$ forms an increasing arithmetic sequence? I ...
4
votes
1answer
42 views

How can I solve $y^4 = 5 \pmod{11\times19}$ with legendre?

Solve $y^4 = 5 \pmod{11\times19}$ I'm trying to let $y^2=A$ then $A^2=5 \pmod{11\times19}$. And solve this problem then $A= 104,-104,28,-28 \pmod{11\times19}$ Then should I solve this problem for ...
1
vote
2answers
27 views

Proof about the quotient remainder theorem by indirect proof

Suppose that every integer can be written in the form $6k+r$ where k is an integer and r is one of the numbers 0,1,2,3,4,5. a) Show that if $p=6k+r$ is a prime different from 2 and 3, then $r=1$ or $...
0
votes
0answers
15 views

How can I prove this is a reduced residue system?

The problem is [Let m>=3 be a positive integer and let Zm* = {s1,s2,s3...,sφ(m)} denote the standard reduced set of residues modulo m. Derive that s1+s2+...+sφ(m)=φ(m)/2 * m] So I tried to make set T:...
0
votes
1answer
27 views

Well ordering axiom problem

Show that if a and b are positive integers, there is a positive integer n such that $na>b$. Hint: Consider the differences $b-na$, and apply the well ordering axiom. I have no approach yet. My ...
1
vote
1answer
69 views

Maximal bounds for a variable

If $p$ and $q$ are distinct prime numbers, then there are integers $x_0$ and $y_0$ such that $$1 = px_0+qy_0.$$ Determine the maximum value of $b-a$, where $a$ and $b$ are positive integers with the ...
1
vote
0answers
28 views

Explaining a Series Expansion for the Divisor Function

The "sum-of-divisors" function, defined as $\sigma(n)=\sum_{d\,\mid\,n}d$, can be expressed as $$\sigma(n)=\sum_{i=1}^n\sum_{j=1}^i\cos\Big(2\pi n \frac{j}{i}\Big)$$This expansion makes logical sense. ...
5
votes
1answer
177 views

Inequality with a rational polynomial

Let $$P(x)=x^{n-1}+a_{n-2}\,x^{n-2}+a_{n-3}\,x^{n-3}+\cdots+a_0\in\mathbb{Q}[x]$$ be a monic rational polynomial of degree $n-1$. I want to show that, for every set of $n$ distinct integers $\{x_1,...
2
votes
2answers
81 views

Find all solutions $10^x=11^y-1$

I tried to solve this like this. $x=1,y=1$ is solution. And Let $x=a y=b\, (a\geq 1,b\geq2)$ Then, $11$ can divide $11^b = 10^a+1$ so $10^a = 10 \pmod{11}$ but order of $11(10) = 2$. Then there ...
7
votes
2answers
182 views

Find number of integral solutions of a*b*c*d = 600

The number of ordered solutions comes out to be 800. I need to find the number of distinct solutions but I'm stuck at calculating the possible combinations. Any ideas on how to proceed further?
0
votes
1answer
92 views

Determine the maximum value of $b-a$, where $a$ and $b$ are positive integers with the following property

If $p$ and $q$ are distinct prime numbers, then there are integers $x_0$ and $y_0$ such that $1 = px_0+qy_0$. Determine the maximum value of $b-a$, where $a$ and $b$ are positive integers with the ...
4
votes
4answers
137 views

Find the highest power of $4$ in $82! + 83!$

I'am only getting $4^{13}$ as answer, but the correct answer is $40$. What am I missing?
3
votes
0answers
62 views

Minimum number of steps to reduce a number to zero.

I am trying to solve a problem which is described below: Given a number n reduce it to 0 in a minimum number of steps using the 2 operations below:1. n can be changed to max(a,b) where n=a*b (a ...
-1
votes
0answers
14 views

trouble undestanding the proof for the therom “If x is element of N and x != 1, then there is a unique y so that x = y'.”

give the following axioms The following theorem is proven Im having trouble understanding the sentence from "if x=1 then x' element of N ..." up to "and by definition of A, x' element of A." ...
1
vote
1answer
68 views

How can I prove this relation?(Number-Theory)

$\gcd(ord(a),ord(b))=1,\: a^i=b^j \mod n$. Then, $a^i=1 \mod n,\: b^j=1 \mod n$ How can I prove it? This is what I tried. Let $ord(a)=p, ord(b)=q$. Then $a^p=1\mod n,\: b^q=1\mod n$. And $p/\gcd(p,...
0
votes
2answers
34 views

How can I solve binomial congruent equations?

[Determine whether or not the quadratic congruence $2x^2+5x-9=0\pmod {101}$ is solvable.] I make it to perfect square form and use Legandre symbol. $2(x+77)^2 = 60 \pmod{101}$ Is there any ...
6
votes
2answers
116 views

Prove that $M = \mathbb Z^+$

Let $M$ be a nonempty subset of $\mathbb Z^+$ such that for every element $x$ in $M,$ the numbers $4x$ and $\lfloor \sqrt x \rfloor$ also belong to $M.$ Prove that $M = \mathbb Z^+$. Suppose $a \in ...
10
votes
1answer
147 views

When is $\displaystyle\sum_{i=1}^n a_i^{-2}=1$?

For which natural numbers $n$ do there exist $n$ natural numbers $a_i\ (1\le i\le n)$ such that $\displaystyle\sum_{i=1}^n a_i^{-2}=1$? I didn't see an easy way of solving this. There is a solution ...
1
vote
0answers
18 views

What are the applications of quantum shuffle multiplication?

I am writing a research paper on quantum shuffle multiplication, and there is just one piece that I'm missing: I want to give one or several examples of its applications, and so far I have not been ...
2
votes
1answer
59 views

Prove that the product is not an integer

Let $p$ be a prime number and $n$ a positive integer. Prove that the product $$N = \frac{1}{p^{n^2}} \prod_{i=1;2 \nmid i}^{2n-1} \left[((p-1)i)! \binom{p^2 i}{pi}\right]$$ Is a positive integer ...
0
votes
1answer
35 views

Unique pythogorean primitive for each pythagorean triplet?

I am not sure if there corresponds a unique pythogorean primitive for each pythogorean triplet that is not a primitive. Whatever might be the case, a proof would be great (since I failed to prove or ...
2
votes
2answers
95 views

Prove that there are infinitely many primes $p$ such that $\left(\dfrac{p}{5} \right) = 1$ [duplicate]

Let $\left(\dfrac{a}{p}\right)$ denote the Legendre symbol. Prove that there are infinitely many primes $p$ such that $\left(\dfrac{p}{5} \right) = 1$. Since there are infinitely many primes there ...
4
votes
2answers
65 views

Prove that if $p$ is a prime number then $\binom{p-1}{k}\equiv (-1)^k\pmod{p}$

Prove that if $p$ is a prime number then $\binom{p-1}{k}\equiv (-1)^k\pmod{p}$. What can be said about $\binom{p+1}{k} \pmod{p}$? I thought about expanding $\dbinom{p-1}{k} = \dfrac{(p-1)!}{k!(p-1-k)...
2
votes
0answers
50 views

Simplifying a Double Summation

Let $f_n(k)$ be defined as $$f_n(k)=\sum_{i=1}^n\sum_{j=1}^i\left(\frac{j}{i}\right)^k$$ Can $f_n(k)$ be simplifying down to an expression without summations? By simply graphing $f_n(k)$, it is clear ...
0
votes
1answer
23 views

Maximum length of subset such that all elements are coprime

Given an array, we have to find the length of maximum subset such that all elements of that subset are coprime. That is for $a[i],a[j]$ belonging to subset $\gcd(a[i],a[j]) = 1$ for all distinct $i,j$....
2
votes
1answer
43 views

How do I find the sum using non-brute force method?

How many number $X$ less than $350$ exist such that the sum of the number of divisors of X and the number of divisors of the square of $X$ is $60$ I know how to find the number of divisors without ...
1
vote
1answer
29 views

Number of distinct equivalence classes of $\mathbb Z_n$ of the “ associate ” equivalence relation

Define an equivalence relation on $\mathbb Z_n$ as : For $a,b \in \mathbb Z_n $ , $a\sim b$ iff $\exists k \in U_n=\mathbb Z_n^{\times}$ such that $a=kb$ (i.e. $a,b$ are related if they are "...
1
vote
1answer
50 views

Primes is in P, proof of hendrik Lenstra Jr. lemma

In the paper describing AKS primality test : http://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf On page no. 8 Lemma 4.7 last paragraph, I cannot understand how number of ...
1
vote
2answers
48 views

Elliptic curves over $\mathbf{F}_q$ with $q = p^{2m}$

I am reading Washingtons book about elliptic curves and struggling with an exercise there (4.9), which is the following: Let $E$ be an elliptic curve over $\mathbf{F}_q$ with $q = p^{2m}$. Suppose ...
0
votes
1answer
28 views

Question about multiplicative arithmetic functions

Let $f,g:\Bbb N\to \Bbb C$ be multiplicative arithmetic functions, i.e. $$\gcd(m,n)=1\implies f(mn)=f(m)f(n)$$ and same for $g$. We can also assume $f(1)\neq 0$ and $g(1)\neq 0$ if necessary. How can ...
0
votes
1answer
25 views

How prove this $a^{km^n}\equiv 1\pmod{m^{n+1}}$

Let $a,k,m,n$ be positive integers,if such $$\color{red}{a^k\equiv 1\pmod m}$$ show that $$\color{blue}{a^{km^n}\equiv 1\pmod{m^{n+1}}}$$ Let $a^k=mq+1$,then $$a^{km^n}=(mq+1)^{m^n}=1+m^{n+1}q+\binom{...
1
vote
2answers
62 views

Non-algebraic structures?

We call group, ring, field,... "algebraic structures". Do we have similar analogue for transcendental numbers? If not, then how do we study interactions between various transcendental numbers? Also, ...
-1
votes
0answers
25 views

Problems using number theory and groups in Cryptography [closed]

I am writing a research paper in maths, and have experience with undergraduate level number theory and group theory. I read about applications of these concepts in cryptography which look really ...
1
vote
1answer
35 views

Is there an integer z such that $255z\equiv 7\pmod {633}$?

I used the extended euclidean algorithm to "Find integers x and y such that $633x + 255y = 6$, or explain why none exist." And found that $6x = -58$ and $y = 144$. Now I'm stuck on the follow up ...
0
votes
0answers
54 views

Confusion about Saibians article about primes

Here : https://sites.google.com/site/largenumbers/home/1-5/2 Saibian claims that it was proven that infinite many twin primes exist. Did I miss something ? Isn't the twin-prime-conjecture open ?...
0
votes
1answer
34 views

Cubic reciprocity proof

I'm working on the proof of cubic reciprocity. I don't understand the proof of the following theorem. Suppose that $N(\pi)=p$ congruent of 1 modulo 3. Among THE associate of $\pi$ exactly one is ...
7
votes
1answer
110 views

A question about arithmetic progressions and prime numbers

I took number $3$ and observed: $3$ is an arithmetic progression of length one. $3,5$ is an arithmetic progression of length two. $3,5,7$ is an arithmetic progression of length three. Then I took ...
3
votes
1answer
50 views

Prime numbers between two multiples of numbers

I am wondering about the following question. Do there exist infinitely many prime numbers $p$ such that there exist integers $m,n$ with $5(m+1) \geq 7n$ and $$5m < p < 7n?$$ If not, what ...
0
votes
2answers
74 views

Find the number which the given equation is true [closed]

Find the number which the given equation is true $$\overline{abcd}=a^a+b^b+c^c+d^d$$
3
votes
4answers
118 views

How to calculate $9^{47^{51}} \mod 67$?

I've looked at some other related things on here, but this seems a little more complicated with the double exponentiation. Is there a general algorithm to calculate $a^{c_1^{c_2^{...^{c_n}}}} \mod p$ ...
1
vote
1answer
56 views

Prove that a Fermat Number cannot be a Carmichael Number?

Prove that a Fermat Number cannot be a Carmichael number: Fermat numbers are of the form $2^{2^n}+1$ and $F$($n$) denotes the $n$th Fermat number. If $F$($n$) is a Carmichael number, that would mean ...
0
votes
2answers
88 views

Prove *directly*: Even perfect squares have even square roots.

Is it possible to prove directly that even perfect squares have even square roots? Or, symbolically: $\forall n \in \mathbb{Z},\ \ n^2 \text{ is even } \Rightarrow n \text{ is even }$ The indirect ...
1
vote
1answer
85 views

Counting the number of partitions

Let $P$ be a set of $7$ different prime numbers and $C$ a set of $28$ different composite numbers each of which is a product of two (not necessarily different) numbers from $P$. The set $C$ is divided ...