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

learn more… | top users | synonyms (1)

0
votes
1answer
74 views

equation $x^4 + y^4 = z^4$

Diophantine equations that are insoluble in $\mathbb{Z}$ may become soluble in finite integral domains. Show that \begin{equation*} x^4 + y^4 = z^4 \end{equation*} is soluble (as a congruence) in ...
0
votes
0answers
33 views

First whole number solution for linear equation

I have a simple linear equation with 2 variables(both whole numbers) $$\left ( 840x + 3 \right )= 9y$$ I need to find the minimum value of x for which this equation holds. Just by looking at the ...
0
votes
1answer
44 views

question on two-square problem.

Let $A_1, A_2$ be two quadratic residues of ($4k + 3$)-prime $p$ that satifsy $0 < A_1 < A_2 < p$. Prove that $A_1 + A_2 \equiv 0 \pmod p$ is impossible. Illustrate this result with $p = ...
3
votes
3answers
37 views

When $p=3 \pmod 4$, show that $a^{(p+1)/4} \pmod p$ is a square root of $a$

Let $a$ and $p$ be integers such that $p$ is prime, and $a$ is a square modulo $p$. When $p\equiv3\pmod4$, show that $a^{(p+1)/4}\pmod p$ is a square root of $a$. Why does this technique not work when ...
1
vote
1answer
44 views

Find the smallest integer that is divisible by exactly $X$ perfect squares.

Is there a method to find the smallest integer divisible by exactly $X$ perfect squares? Example: find the smallest positive integer divisible by exactly 2015 perfect squares. I've been trying to ...
0
votes
1answer
23 views

Proving $S_1 \subseteq S_2$ for transitive closure

This is one of the problem I have been working from Velleman's How to prove book: Suppose $R_1$ and $R_2$ are relations on $A$ and $R_1 \subset R_2$l (a) Let $S_1$ and $S_2$ be the reflexive ...
3
votes
1answer
45 views

Could all iterates of $s(n)=2n+1$ be composite for some starting $n$?

Let $s(n)=2n+1$ and $\sigma(n)=\{n,s(n),s^2(n),s^3(n),\ldots\}$, where $s^3$ denotes functions composition, $s^3(n)=s(s(s(n)))$. For example $\sigma(11)=\{11,23,47,95,\ldots\}$. As another example ...
2
votes
1answer
51 views

how to prove by induction the $ (1+x)^{n}>1+nx+nx^2$

Prove by induction the formula $ (1+x)^{n}>1+nx+nx^2$ for $x>0$ real number and $n\ge 3$ my try : multiply both sides by $(1+x)$ gives $ (1+x)^{n+1}>1+(n+1)x+(2n+nx)x^2$ have I done ...
0
votes
1answer
35 views

Show the following statement

Let $S_a$ the product of the first a primes. If $s_a (n)= \sum \limits_{d|(n,S_a)} \mu(d)$ = 1 , if n has no prime factors < a and $0$ otherwise. Then it should be showed $\sum \limits_{n \le b} ...
0
votes
3answers
44 views

Negative number to the power of…

We know that negative number to the power of any integers or some fractions will always have a solution. Is it possible for us to solve $(-2)^\frac 13$ or $(-2)^e$, by modifying/extending our ...
2
votes
0answers
40 views

Prove that the highest power of $n$ contained in $(n^r-1)!$ is $\frac{n^r-nr+r-1}{n-1}$.

Prove that the highest power of $n$ contained in $(n^r-1)!$ is $\frac{n^r-nr+r-1}{n-1}$. Attempt: I want to use the following theorem: The largest exponent of $e$ of a prime $p$ such ...
3
votes
2answers
72 views

Backwards proof of Fermat's Little Theorem

$$\textrm{Let }p \in \mathbb{N}. \textrm{ Show that }\forall n \in \left \{ 1,2,...,p-1 \right \} \textrm{if } n^{p-1} \equiv 1 \mod p \Rightarrow p \in \mathbb{P}$$ This is basically Fermat's ...
3
votes
4answers
67 views

Prove that number of zeros at the right end of the integer $(5^{25}-1)!$ is $\frac{5^{25}-101}{4}.$

Prove that number of zeros at the right end of the integer $(5^{25}-1)!$ is $\frac{5^{25}-101}{4}.$ Attempt: I want to use the following theorem: The largest exponent of $e$ of a prime $p$ ...
1
vote
1answer
39 views

how to solve system of quadratic equations (mod N)

Given a two equations: $${(ax_1 + b)}^2 = c_1 \pmod N$$ $${(ax_2 + b)}^2 = c_2 \pmod N$$ $N=p.q$ $p$ and $q$ are large primes $x_1, x_2$ and $c_1, c_2$ are known Is it computationally feasible to ...
0
votes
0answers
6 views

Unique symmetric multilinear form associated to a form

Let $F(\mathbf{x}) \in \mathbb{Z}[x_1, ..., x_n]$ be a form of degree $d$. In an article I am reading, it says to associate to $F$ the unique symmetric multilinear form $F(\mathbf{x}_1| ... | ...
9
votes
3answers
84 views

Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$.

So the problem states: Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$. I was thinking about trying to prove this using the corollary to ...
2
votes
0answers
40 views

Diophantine eqution with odd prime

HOW to find all possible set of solutions of an equation type $y^p \pm 2 = x^2$, where $p$ is any odd prime High regards to one and all
3
votes
1answer
67 views

Distribution of composite numbers

This question is moved from mathoverflow, there are several excellent answers at mathoverflow which improve my question greatly. For more information, please see the original question posted on ...
-1
votes
3answers
85 views

Prove that $\sqrt{2n}$ is irrational if $n$ is an odd natural number. [closed]

We know that $\sqrt{2}$ is irrational, but how would we go about proving this? I have already attempted to follow the same method of proving this as in the proof of $\sqrt2$ , but I cannot end up ...
3
votes
2answers
52 views

Prove that if $a \mid n$ then $a^2\mid (n + 1)(n − 1) + 1$

I have this review question for an exam and I was hoping someone can help me solve it: Prove that if $a \mid n$ then $a^2\mid (n + 1)(n − 1) + 1$ this is what I have so far, not sure if it is ...
1
vote
0answers
59 views

Determine all natural numbers n and m that satisfying in this equation. [closed]

I'm trying to solve the following question: Determine all natural numbers n and m such that: $$n ^ { n ^ n } = m^m.$$ I don't have any idea about this question. Can somebody help me or give ...
0
votes
2answers
21 views

If $C|a$ and $C|b$ then $C|(ax+by)$

If $c|a$ and $c|b$ then $c|(ax+by)$ where $c,a,b$ are integers Proof: Suppose $c|a$ and $c|b$ then we can represent as the following: $a=cx$ where $x$ is an integer $b=cy$ where $y$ is an integer ...
2
votes
2answers
60 views
2
votes
1answer
29 views

What is the sum of the quadratic residues of prime $p=4k + 3$?

If prime $p=4k + 1$ we know that if a is a quadratic residue then $-a$ is a quadratic residue, So there are $(p - 1)/4$ pairs of integers whose sum is $p$. So the sum over all quadratic residues is ...
1
vote
4answers
73 views

Let $a,b$ be relative integers such that $2a+3b$ is divisible by $11$. Prove that $a^2-5b^2$ is also divisible by $11$.

The divisibility for $11$ of $a^2 - 5b^2$ can be easily verified; in fact: $$a \equiv \frac {-3}{2}b \pmod {11}$$ therefore $$\frac {9}{4}\cdot b^2 - 5b^2 = 11(-\frac{b^2}{4}) \equiv 0 \pmod {11}.$$ ...
5
votes
0answers
63 views

Show that for a given $s$ there are a finite number of Fibonacci number of form $n^2+s$

It is well known that the last Fibonacci number $F_k$ such that $\exists \ n \in \Bbb{N} : F_k = n^2$ is $144$. Thus there are only $4$ perfect squares among the Fibonacci sequence (assuming you ...
1
vote
0answers
64 views

$5^x \equiv 1520 \pmod {9797}$ [duplicate]

How do you solve this? What does mod mean and how will I solve it? I understand that it can be solved but how? 5 to some exponent equals the (mod of 9797) what is the answer to this?
0
votes
1answer
30 views

How to prove this by induction

Prove by induction the following equality : $\ 1-4+9-16+\cdots+(-1)^{n+1} n^2 = (-1)^{n+1}(1+2+3+\cdots+n) $ I don't know what to do in this case, I know what to do in general but can do this one
12
votes
1answer
103 views

$CL(O_S) \cong \mathbb{Z}/3\mathbb{Z}$.

Let $F = \mathbb{Q}(T)$ and let $X$ be the set of all places of $F$, and let $S = \{w\} \subset X$ where $w$ is the place of $F$ corresponding to the maximal ideal $(T^3 - 2)$ of $\mathbb{Q}[T]$. Let ...
1
vote
9answers
77 views

Find integers $m$ and $n$ such that $14m+13n=7$.

The Problem: Find integers $m$ and $n$ such that $14m+13n=7$. Where I Am: I understand how to do this problem when the number on the RHS is $1$, and I understand how to get solutions for $m$ and ...
20
votes
5answers
2k views

Where does the constant increase by 2 of differences between integer square values come from?

$1^2 = 1$, $2^2 = 4$, $3^2 = 9$, $4^2 = 16$, $5^2 = 25$, etc... Looking at the difference between those square values, we get: 3, 5, 7, 9, etc... The difference from one (integer) square to the ...
-1
votes
0answers
27 views

Can this equation be solved given integer $n$ and constraint on $k$ and $e$ to be rational? $2k (e^2-n) + k^2 = 2n e^2 - 2n^2$

I am looking for a general way to solve for rational $e,k$ given integer $n$ $$2k (e^2-n) + k^2 = 2n e^2 - 2n^2$$ Repeating fraction methods are fine I just need a rational number for $k$ and ...
-1
votes
3answers
56 views

Number Theory Proof regarding phi [closed]

Let $m =p_1p_2$ such $\gcd(k,\phi(m))=1$ and $kl \equiv 1 \pmod {\phi(m)}.$ Prove that $(a^k)^l \equiv a \pmod m $ even if $\gcd(a,m)$ not equal to $1$.
4
votes
1answer
38 views

Describe the set of odd primes such that $\left(\frac{-5}{p}\right) = 1$ (Legendre Symbol)

Okay, so $\left(\frac{-5}{p}\right) = 1$. I am assuming that I can start this by saying $\left(\frac{-5}{p}\right) = \left(\frac{5}{p}\right) \times \left(\frac{-1}{p}\right)$. There are well ...
0
votes
2answers
50 views

Is the function $f : {\Bbb Z}\times{\Bbb Z} \to {\Bbb Z}$ where $f(m,n) = 2n-m$ onto or one-to-one? [closed]

I am not sure where to start with this one. How can I determine if the function $f : {\Bbb Z}\times{\Bbb Z} \to {\Bbb Z}$ where $f(m,n) = 2n-m$ is onto, one-to-one, or both?
4
votes
4answers
48 views

First number $\ge n$ that is divisible by $k$?

Is there a good way to compute the first value $\ge n$ that is divisible by $k$? Right now I am computing $\left\lfloor\frac{n}{k}\right\rfloor k$ but it doesn't always work.
-1
votes
0answers
46 views

Cos(a) simplification or reduction of?

"2" to the power of "a" to the power of "cos(a)" as the index. ""cos(a)"" as the radicand. ... is it possible to rewrite with ""no"" cos(a) in the above expression...
0
votes
1answer
49 views

Determining all the positive integers $n$ such that $n^4+n^3+n^2+n+1$ is a perfect square.

I successfully thought of bounding our expression examining consecutive squares that attain values close to it, and this led to the solution I'll post as an answer, which was the one reported. ...
3
votes
3answers
67 views

Calculate possible values of $a^4$ mod $120$.

Calculate possible values of $a^4$ mod $120$. I don't know how to solve this, what I did so far: $120=2^3\cdot3\cdot5$ $a^4 \equiv 0,1 \pmod {\!8}$ $a^4 \equiv 0,1 \pmod {\!3}$ $a^4 \equiv 0,1 ...
0
votes
2answers
46 views

Solving the equation in natural numbers

How can I find the solutions in natural numbers for the following equation? $$a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}=b$$ Where $x_{1},...,x_{n}$ are unknown. I want to find the whole of solutions ...
3
votes
1answer
35 views

Universal property of natural number semi-ring

I asked a question similar to the one I am about to ask, and I think I got a satisfactory answer. However, this time I have some more specific question. Let a semiring $(R,+,\times)$ be an algebraic ...
0
votes
0answers
22 views

Find pseudo-square mod $n$

The definition of a pseudo-square in this case is let $n=pq$ where $p$ and $q$ are primes. A pseudo-square mod $n$ will be defined as a number $a$ such that $(\frac{a}{p}) = (\frac{a}{q}) = -1$ ...
2
votes
2answers
45 views

To find the smallest integer with $n$ distinct divisors

For example, if $n=20$, how can I find the smallest integer which has exactly $20$ distinct divisors? Can someone give me some hints?
0
votes
4answers
57 views

Find all positive integers $a, b$ such that $ab = a - 5b + 20$

$$(a+5)(b-1)=ab-a+5b-5=20-5=15.$$ So, both $a + 5$ and $b-1$ divide $15$. Then, $a + 5$ is one of $15, -15, 3, -3, 5, -5, 1, -1$, so $a$ is one of $10, -20, -2, -8, 0, -10, -4, -6$ and $b – 1$ is ...
1
vote
4answers
59 views

Why the $GCD$ of any two consecutive fibonnaci numbers is $1$?

Note: I've noticed that this answer was given in another question, but I merely want to know if the way I'm using could also give me a proof. I did the following: $$F_n=F_{n-1}+F_{n-2} \\ ...
6
votes
1answer
70 views

Find all pairs of positive integers $(m,n)$ such that $2^{m+1}+3^{n+1}$ is a perfect square [duplicate]

Find all pairs of positive integers $(m,n)$ such that $2^{m+1}+3^{n+1}$ is a perfect square My attempt so far Any perfect square is $0,1$ in mod 4, so $n+1$ must be even : $$2^{m+1}+3^{2r}=k^2$$ ...
2
votes
1answer
21 views

Show for all primes $p>11$ there are two consecutive quadratic residues [duplicate]

I am supposed to use this fact to help prove it. If $p$ is an odd prime, then at least one of the numbers $2,5,10$ is a quadratic residue mod $p$ I can prove this by saying let $(\frac{10}{p}) = 1$ ...
3
votes
1answer
37 views

Set of positive integers with unique sums

What I'm looking for is the name of a type of number set. Given a number T (for total) and a set of positive integers S, I want to uniquely identify the subset of S that sums to T. All sets containing ...
5
votes
4answers
103 views

What is $3^{43} \bmod {33}$?

I just took math final and one of the question was Find $3^{43}\bmod{33}$. So, I used Euler's function; $\phi(33)=20$. $3^{20}\equiv 1\pmod{\!33}$ By using this fact, I got $27$. One ...
1
vote
1answer
32 views

Prove that if $\{1^5,2^5,\ldots, (pq)^5\}$ is a complete residue system mod $pq$, then $\{1^5,2^5,\ldots,p^5\}$ is a complete residue system mod $p$.

Let $p,q\ge 2$ be coprime positive integers. Prove that if $\{1^5,2^5,\ldots, (pq)^5\}$ is a complete residue system mod $pq$, then $\{1^5,2^5,\ldots,p^5\}$ is a complete residue system mod $p$. ...