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
43 views

Proof about diophantine equation

show that the diophantine equation $$x^2-y^2=N$$ is solvable in nonnegative integers x and y if and only if N is odd or divisible by 4. Show further that the solution is unique if and only if $|N|$...
0
votes
2answers
29 views

proof about rational roots test theorem

show that if the reduced fraction a/b is a root of the equation $$c_0x^n+c_1x^{n-1}+...+c_n=0$$ where x is areal variable and $c_0,c_1,....,c_n$ are integers $c_0\neq 0$ then $a|c_n$ and $b|c_0$ ...
1
vote
1answer
176 views
+50

Why it is impossible for primitive Pythagoras triplets in integers to be all as powerful numbers?

I had seen an elementary proof for Fermat's last theorem at Quora. I had checked all the steps (around one page only),where I couldn't catch any error, but I was confused about the last step only ...
2
votes
3answers
83 views

$\binom{n}{1},\binom{n}{2},\ldots ,\binom{n}{n-1}$ are all even numbers.

Consider the binomial coefficients $\binom{n}{k}=\frac{n!}{k!(n-k)!}\ (k=1,2,\ldots n-1)$. Determine all positive integers $n$ for which $\binom{n}{1},\binom{n}{2},\ldots ,\binom{n}{n-1}$ are all even ...
1
vote
1answer
48 views

Finding the maximum value of $n$ [closed]

What's the maximum value for $n$ for which there is a set of distinct positive integers $k_{1}, k_{2}, ... , k_{n}$ for which $k_{1}^{2} + k_{2}^{2} + ... + k_{n}^{2} = 2002$
0
votes
0answers
30 views

Devisor Function formula

I can calculate devisor function d(n) from the following formula but I do not know if it can be accepted in the world of Math $$d(n)=\sum_{n=1}^x 0^{sin^2(\frac{\pi*x}{n}))}, x \ge 1$$ example: ...
3
votes
3answers
164 views

A certain unique rotation matrix

One can find that the matrix $A=\begin{bmatrix} -\dfrac{1}{3} & \dfrac{2}{3} & \dfrac{2}{3} \\ \dfrac{2}{3} & -\dfrac{1}{3} & \dfrac{2}{3} \\ \...
5
votes
3answers
53 views

Proving the Well-Ordering Principle for Natural Numbers

I know the WOP is treated like axiom of a natural number, but I was curious if I can prove WOP defined for the set of natural numbers N by following: Suppose A is a subset of N, which then obeys all ...
2
votes
0answers
51 views

Finding solutions in modulo

If I know $x$ modulo m and n, then under what conditions on m,n and p will i necessarily know $x$ modulo p? My initial guess is only in trivial cases, i.e. p is a multiple of m or n, but i cant seem ...
2
votes
1answer
76 views

An equation in $\mathbb{Z}$

I want to solve ${y^2}=x^4+x^3+x^2+x+1$ in $\mathbb{Z}$ . I can find four solutions. Is there another solution? I know that there are six solutions. $$(-1, \pm 1)\quad,\quad(0, \pm 1)$$ My try \begin{...
3
votes
1answer
106 views

Prove that there exist positive integers $a_1, a_2, …, a_n\ne 1$ such that $a_1a_2…\hat a_i…a_n \equiv 1 \pmod {a_i}$, for $i=1,2, …n$.

Let $n\ge 3$ be an integer. Prove that there exist positive integers $a_1, a_2, ..., a_n$ other than 1 such that $a_1a_2...\hat a_i...a_n \equiv 1 \pmod {a_i}$, for $i=1,2, ...n$. Here, $\hat a_i$ ...
2
votes
1answer
40 views

Values of Polynomial in $\mathbb{F_{2^n}}$

$ \phi~:~ \mathbb{F_{2^n}} \rightarrow D, ~\phi(X)= X+X^2+...+X^{2^{(n-1)}}$ Show that $D=\{0,1\}$ for any n and $\phi(X)=0$ exactly for half of the $X \in \mathbb{F_{2^n}}$. Hi, got a bit rusty ...
5
votes
1answer
114 views

Is there a prime of the form $11^k+k^{11}\ $?

Is there a natural number $k\ge 1$, such that $11^k+k^{11}$ is prime ? I checked the numbers upto $k=3000$ and did not find a prime number. On the other hand, for $k=76$ and for $k=142$, there is no ...
1
vote
1answer
33 views

Proof about euclidean algorithm

When calculate the gcd of a and b by using the greatest common divisor, call the remainders along the process $r_1,r_2....etc$. Show that each nonzero remainder $r_m$ with $m \geq 2$ is less than $r_{...
-2
votes
0answers
21 views

Fibonacci pseduprime in mod [closed]

I am so afraid to look at this question as this troubling me. looking for serious help For a prime $p$, $f_n$ is Fibonacci series, can we prove $p|f_{p-1}$ and $p|f_{p+1}$ when $p = 3(mod 10)$ or ...
1
vote
3answers
50 views

Proof about property of the gcd

if $m|a$ and $m|b$ then $(a/m,b/m)=(a,b)/m$ proof show $(a/m,b/m)\leq (a,b)/m$ and $(a/m,b/m) \geq (a,b)/m$ Let $(a,b)=d$, so by bezout's identity there exists intergers x,y such that ax+by=d $$ax+...
4
votes
4answers
96 views

What is $\gcd(12345,54321)$?

What is $\gcd(12345,54321)$? I noticed that after trying $\gcd(12,21),\gcd(123,321),$ and $\gcd(1234,4321)$ that they are all less then or equal to $3$. That leads me to question if there is an easy ...
1
vote
1answer
40 views

How many polynomials are squarefree?

Of course, this depends on the field, and how we measure "how many," but it seems I cannot find an answer to this except over finite fields. My question specifically is If we have a field $F = \...
0
votes
1answer
66 views

Proof about GCD

Prove The GCD of more than two numbers, defined as that positive common divisor which is divisible by every common divisor, exists and can be found in the following way. Let there n numbers $a_1,a_2,.....
3
votes
2answers
39 views

proof about a lemma of divisibility

Show that if $a|b$ and $b \neq 0$ then $|a| \leq |b|$ Approach: Assume $|a| > |b|$ and $b=ak$ for some integer k $$|a| > |ak|$$ which is a contradiction becasuse $|a||k|=|ak|>|a|$ or $|ak|=...
1
vote
1answer
117 views

On solving the Collatz conjecture

This method may be kinda inefficient as solving each step may require $O(n!)$ computational time, but for $n$ Collatz operations isn't it possible to disprove the existence of a cycle of $n$ ...
2
votes
2answers
78 views

Find all pairs such that $x^2 y + x + y$ is divisible by $xy^2 + y + 7$

Find all pairs $(x, y)$ of positive integers such that $x^2 y + x + y$ is divisible by $xy^2 + y + 7$. If there are too many to write, write a generic form. I was thinking of rewriting the ...
4
votes
1answer
77 views

Pattern in numbers

I bumped into this mathematical calculation while driving my car. With lot of traffic jams and lot of time to kill, I did some scrambling of the registration numbers of the cars in front of me. I ...
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
25 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
107 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?
2
votes
0answers
48 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
86 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
81 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
28 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 ...
2
votes
1answer
67 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
187 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
82 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
183 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
139 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
64 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
76 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
118 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
148 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
61 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
37 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 ...