Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

0
votes
0answers
25 views

Prove that if $x^3 + y^3 = z^3$, and $x$, $y$, $z$ are quadratic integers in $\mathbb Q[\sqrt{−3}]$, then $λ$ must divide one of $x$, $y$, or $z$.

Let $λ = (3 + \sqrt{−3})/2 ∈ Q[\sqrt{−3}]$. Prove that if $x^3 + y^3 = z^3$, and $x$, $y$, $z$ are quadratic integers in $\mathbb Q[\sqrt{−3}]$, then $λ$ must divide one of $x$, $y$, or $z$.
6
votes
1answer
172 views

What Is The Smallest Solution to $7x^5=11y^{13}$?

I started teaching myself Number Theory from a pretty basic textbook and I got completely stuck with this problem. Let $x$ and $y$ be two non-zero natural numbers such that $7x^5=11y^{13}$ . The ...
2
votes
3answers
86 views

Prove that $p\mid a^2+b^2\,\Rightarrow\, p\equiv 1\pmod{\! 4}$

Let a prime number $p$ divide $a^2+b^2$ with some $a,b \in \left\{ 1,2, \ldots , p-1 \right\}$ Prove that $p\equiv 1 \pmod{4}$. Is the converse true? I know that $a^2+b^2\equiv 0 \pmod{p}$ and I ...
3
votes
6answers
64 views

Prove that $2^n(n!)^2 \leq (2n)!$

Prove that $2^n(n!)^2 \leq (2n)!$ One can also use the following result to prove the above: $2 · 6 · 10 · 14 · · · · · (4n − 2) = \frac{(2n)!}{ n!}$. The above relation gives, $(2n)!=2^n n! ...
2
votes
1answer
70 views

There are an infinite number of primes $p$ of the form $p=2^2+a^2$, where $a$ is also a prime [closed]

A claim from David Burton's Elementary Number Theory: There are an infinite number of primes $p$ of the form $p=2^2+a^2$, where $a$ is also a prime.
0
votes
0answers
48 views

Find the values of $n \leq 7$ for which $n! + 1$ is a perfect square.

The following problem is from p. 7 of the "Preliminaries" section in David Burton's Elementary Number Theory (7th ed.). Find the values of $n \leq 7$ for which $n! + 1$ is a perfect square (it is ...
-2
votes
5answers
54 views

Solving $7a + 8 \equiv 5 \pmod{11}$

Solve $7a + 8 \equiv 5 \pmod{11}$. I am having trouble answering this math problem. The final answer should work out to be $a = 9$ but I quite simply don't know to get that answer.
3
votes
1answer
39 views

Prove that a prime $p$ can be represented as the difference of two cubes if and only if it is of the form $p = 3k(k+1) + 1$ for some $k$.

This is a question from David Burton's Elementary Number Theory, p. 280, under "Representation of Integers as Sums of Squares." Prove that a prime $p$ can be represented as the difference of two ...
3
votes
6answers
124 views

(14^2014)^2014 mod 60 without a calculator

Calculate without a calculator: $\left (14^{2014} \right )^{2014} \mod 60$ I was trying to solve this with Euler's Theorem, but it turned out that the gcd of a and m wasn't 1. This was my ...
2
votes
1answer
37 views

What is an “arithmetic progression”?

Today, while doing my math problems on polynomials, I came across the phrase "arithmetic progression." Despite trying hard, I just can't find out the meaning of this phrase and cannot solve my ...
8
votes
3answers
55 views

Prove that if $n$ is a product of two consecutive integers, its units digits must be $0,2, $or $6$

Prove that if $n$ is a product of two consecutive integers, its units digits must be $0,2,$ or $6$. I'm having a hard time with the $0,2,6$ and part but here is what I have so far. Since $n$ is ...
2
votes
2answers
194 views

Making change with prime-valued coins

Am I understanding this question correctly and how do I approach these problems? In Numberland, the unit of currency is the El (E). The value of each Numberlandian coin is a prime number of Els. So ...
11
votes
1answer
243 views

A question on the remainders of integer division

This is a question on the remainders of integer division from my student. Notations. Let $p$ be a positive odd prime integer. We write $r_{i,j}$ for the remainder of $i \times j \div p$. Now for an ...
2
votes
2answers
34 views

Needing help finding the least nonnegative residue

$2^{47} \bmod 23$ $776^{79} \bmod 7$ $12347369^{3458} \bmod 19$ $5^{18} \bmod 13$ $23^{560} \bmod 561$ I really don't understand how to calculate the ones to powers. Could anyone explain how to ...
1
vote
3answers
45 views

Find the least nonnegative residue of $3^{1442}$ mod 700

So I have that $700=7\cdot2^2\cdot5^2$ and I got that $3^2\equiv1\pmod2$ so then $3^{1442}\equiv1\pmod2$ also $3^2\equiv1\pmod{2^2}$ so $3^{1442}\equiv1\pmod{2^2}$ which covers one of the divisors of ...
4
votes
0answers
57 views

Find all positive values for j,k,l such that j, k, l are positive integers and (j-k)|l, (k-l)|j, (l-j)|k.

Find all possible values of $j,k,l$ such that $j, k, l$ are positive integers and $(j-k)|l, (k-l)|j, (l-j)|k$. As I understand that using divisibility properties, it is possible to come to some ...
1
vote
1answer
33 views

Counting the number of integers $x$ in a sequence of $30a$ consecutive integers where $\gcd(x(x+2),30)=1$ and $p \mid x(x+2)$ where $p \ge 7$

I was writing a computer program and I found that for all sequences that I tested the number of $x$ in a sequence of $30a$ consecutive integers for a prime $p$ is less than or equal to: ...
0
votes
2answers
58 views

Demonstrating solutions to two functional equations

Find examples (the more the better) of functions $f: \mathbb{Z} \to \mathbb{C}$ satisfying the relations $f(x+y) = f(x) + f(y)$ $f(xy) = f(x)f(y)$ I have only $f(x)= ax$ $f(x)= x^a$ This task ...
4
votes
2answers
92 views

Euler Fermat with double exponent [duplicate]

I have to calculate $$ 3^{{2014}^{2014}} \pmod {98} $$ (without calculus). I want to do this by using Euler/Fermat. What I already have is that the $\gcd(3, 98) = 1$ so I know that I can use the ...
2
votes
1answer
33 views

Why is $c+q$ still a primitive root modulo $q$?

Question: Let $p$ and $q$ be distinct odd prime numbers. By considering primitive roots, we need to show $\exists c\in\mathbb{Z}$ with the property that: $\bullet$ $c^n\equiv 1\pmod{p}$ whenever $n$ ...
0
votes
2answers
50 views

Find the least nonnegative residue of $68^{105} \pmod{13}$.

I did a problem before this, which was finding the least nonnegative residue of $2^{204} \pmod{13}$. Because $2^{6} ≡ 1 \pmod{13}$, I said that $(2^{6})^{34}≡1^{34} \pmod{13}$, and so I concluded that ...
3
votes
5answers
64 views

The residue of $9^{56}\pmod{100}$

How can I complete the following problem using modular arithmetic? Find the last two digits of $9^{56}$. I get to the point where I have $729^{18} \times 9^2 \pmod{100}$. What should I do from ...
0
votes
0answers
12 views

Is the Möbius inversion applicable in the case of number functions with values in $Q(x)$

I am looking for the cause of an erroneous calculation I did the details I cant present here. I guess a "Möbius inversion" I apply might be the cause. Normally the Möbius inversion is valid for ...
3
votes
0answers
43 views

prime divisor propertyfor Hurwitz integers

The Hurwitz integers $\mathcal{H}_{\mathbb{Z}}$ is a particular subset of quaternions. Define: $$ \mathcal{H}_{\mathbb{Z}} = \left\{ a\frac{1+i+j+k}{2}+bi+cj+dk \ | \ a,b,c,d \in \mathbb{Z} \right\} = ...
1
vote
0answers
22 views

Which pairs of matrices generate $SL(2, \mathbb{Z})$?

I am trying to understand 2 element generating sets of $SL(2, \mathbb{Z})$ certainly these two: $$ \left(\begin{array}{cc} 1 & 1 \\ 0 & 1\end{array}\right) \text{ and } ...
1
vote
2answers
50 views

Show that there are exactly 16 pairs of integers $(x,y)$ such that $11x+8y+17=xy$.

Original problem Show that there are exactly 16 pairs of integers $(x,y)$ such that $11x+8y+17=xy$. My work From case by case analysis I come to know that the equation will hold if and only if $x$ ...
3
votes
1answer
60 views

Find all $c\in\mathbb Z^+$ for which $\exists a,b\in\mathbb Z^+, a\neq b$ with $a+c\mid ab$ and $b+c\mid ab$

Find all $c\in\mathbb Z^+$ for which $\exists a,b\in\mathbb Z^+, a\neq b$ with $\begin{cases}a+c\mid ab\\b+c\mid ab\end{cases}$ For those $c$, prove only finitely many $(a,b)$ exist. ...
1
vote
1answer
48 views

How many solutions to $x^d\equiv a\pmod {p}$?

If $\gcd(d,p-1) = 1$, there is a unique solution to $x^d \equiv a \pmod p$. If $\gcd(d,p-1) > 1$, there are exactly $d$ solutions to $x^d\equiv a\pmod p$. $p$ prime, $d\ge 1$, ...
1
vote
1answer
34 views

Grid Problem Proof

I have a 2x2 grid square say, I can fit a shape like this: Such that there is one missing square. I can arrange this in any way so that the missing square can be located anywhere. I can do ...
15
votes
3answers
756 views

Why is the zero polynomial not assigned a degree?

Yesterday, I read in my textbook, We assign degree to every polynomial and even a non-zero constant is assigned a degree $0$ but $0$ itself is not assigned a degree. Why is that? Why we don't ...
6
votes
2answers
94 views

Only finitely many $a, b$ such that $2+3^n+5^{n^2}=2^a7^b$ for some $n$?

Let $(a,b)$ be a pair of positive integers such that $$2+3^n+5^{n^2}=2^a7^b$$ for some positive integer $n$. Is it true that there are only finitely many such pairs? I don't know the answer to such ...
11
votes
2answers
91 views

If a number is of type $n^n$, how to identify that? Example: 256 is $4^4$, 3125 is $5^5$

If a number is of type $n^n$, how to identify that? Example: 256 is $4^4$, 3125 is $5^5$. I have to write a code for that.
0
votes
2answers
26 views

Does zero constitute an element in the construction of a non-empty set in Number theory?

If my set has '0', is this 'null' or an element in the study of Number theory?
2
votes
1answer
50 views

Euclid's proof for the existence of infinitely many prime

The proof goes like this Suppose to the contrary there exists a list of finite primes which shall be denoted $$\left.\text{$\{$}p_1,p_2\text{,. . . }p_n\right\}$$ The product of all primes in this ...
-1
votes
4answers
78 views

Let $p$ be an odd prime. Show that every prime divisor of $(2^p) - 1$ is greater than $p$. [closed]

Let $p$ be an odd prime. Show that every prime divisor of $(2^p) -1$ is greater than $p$.
0
votes
1answer
85 views

Let $p$ be an odd prime, and let $n$ be an integer not divisible by $p-1$.

Let $p$ be an odd prime, and let $n$ be an integer not divisible by $p-1$. Show that $\sum x^n \equiv 0 \pmod{p}$, when the sum is over all $x$ with $0\le x\le p-1$. Some help with this practice ...
1
vote
1answer
11 views

Congruency proving an integer solution is not possible, Gauss

In Gauss' Disquisitiones Arithmeticae, at the end of Section I he writes that $x^2-8x+6 \: modulo \: 5$ yields the periodic residuals ${1,4,3,4}$, thus $x^2-8x+6 \ncong 0 \: or \: 2 \: modulo \: 5$, ...
3
votes
1answer
36 views

Number of solutions of equations mod $p^n$

Using Hensel's lemma, it is easy to prove that if $p$ is a prime with $p\equiv 1\mod 3$ then the equation $x^2-x+1=0$ has at least two solutions $\mod p^n$ for all $n\geq 1$. Are there more than two ...
6
votes
1answer
115 views

How to prove that $a=z^{p}$ for some $z \in \mathbb{Z_{+}}$?

Claim : If for a positive, composite integer $a$ and an odd prime $p$, such that $\gcd(a,p)=1$, we are given $$ a^{p^{n-2}(p-1)} \equiv 1 \pmod {p^n} \ \forall \ n \geq 2 \ \ ;\ ...
1
vote
1answer
51 views

Prove there do not exist prime numbers $a$, $b$, and $c$ such that $a^3+b^3=c^3$

Prove there do not exist prime numbers $a$, $b$, and $c$ such that $a^3+b^3=c^3$. From what I understand this proof requires a proof by contradiction or contrapositive...
4
votes
5answers
104 views

Proof that $(n^7-n^3)(n^5+n^3)+n^{21}-n^{13}$ is a multiple of $3$.

I proved that $$(n^7-n^3)(n^5+n^3)+n^{21}-n^{13}$$ is a multiple of $3$ through the use of Little Fermat's theorem but i want to know if there exist other proofs(maybe for induction). How can I ...
3
votes
2answers
128 views

Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $.

So we obviously we want $ x^{2} + y^{2} + 1 \equiv 0 ~ (\text{mod} ~ p) $. I haven’t learned much about quadratic congruences, so I don’t really know how to go forward. I suppose you can write it as ...
1
vote
3answers
153 views

Let p be a prime. Consider the equation $\frac1x+\frac1y=\frac1p$. What are the solutions?

Write down the set of distinct solutions and prove your list is complete. $x$ and $y$ are positive integers. I have rewritten it as $\frac{(x+y)}{xy} = \frac1p$, but I don't understand where to go ...
5
votes
7answers
45 views

An integer $a \pmod m$ has inverse if and only if $\gcd(a,m)=1$?

An integer $a \pmod m$ has inverse if and only if $\gcd(a,m)=1$? Why is this? I tried understanding it from my notes but I don't get it. A thorough explanation would be greatly welcome. Thanks for ...
1
vote
1answer
38 views

Analytical solution for $\max{x_1}$ in $(x_n)_{n\in\mathbb{N}}$

Let be $x_1,x_2,x_3,\ldots,$ a sequence of positive integers. Suposse the folowing conditions are true for all $n\in\mathbb{N}$ $n|x_n$ $|x_n-x_{n+1}|\leq 4$ Find the maximun value of $x_1$ I ...
2
votes
2answers
34 views

Cute convergence problem. Proving convergence of sequence regarding reciprocals of least common multiple converges.

This is the first problem of the second day of the $2014$ CIIM. Let $\{a_n\}$ be a strictly increasing sequence of positive integers. Prove the sequence ...
2
votes
1answer
36 views

How to find square and cubes

I want to find the smallest positive integer A in which $$10A$$ is a perfect square and $$6A$$ is a perfect cube Thanks for the hint, I can see now I just needed $$2^5,3^2 , 5^3$$
1
vote
1answer
39 views

How many ordered pairs are there in order for $\frac{n^2+1}{mn-1}$ to be an integer?

For how many ordered pairs of positive integers like $(m,n)$ the fraction $\frac{n^2+1}{mn-1}$ is a positive integer?
1
vote
1answer
28 views

If $p$ is an odd prime with $(p - 1)/2$ primitive roots, is $p$ a Fermat prime?

If $p$ is an odd prime and there are $(p - 1)/2$ primitive roots modulo $p$, then is $p = 2^k + 1$ for some nonnegative integer $k$? This is the converse of a statement that I have already ...