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

learn more… | top users | synonyms (1)

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
78 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
57 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
39 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
39 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$. ...
-1
votes
0answers
32 views

Let $p$ be an odd prime, $D$ be an integer not divisible by $p$. show that $x^2 - y^2 = D (\text{mod } p)$ has $(p-1) $solutions [duplicate]

Let $p$ be an odd prime, $D$ be an integer not divisible by $p$. Show that $$ x^2 - y^2 = D \bmod p $$ has $p-1$ solutions Can somebody help with this problem? Thank you!
0
votes
1answer
52 views

Solutions of the Pell-type equation $x^2-2y^2=-1$

I am assigned to find solutions to the Pell-type equation $x^2-2y^2=-1$. So far, I only have $(7,5), (41,29)$ and $(239,169)$. My question is, is there a general formula to find all its solutions? ...
4
votes
1answer
43 views

Estimate of an exponential sum involving the Von Mangoldt function

Let $f(x)$ be a polynomial in $\mathbb{Z}[x]$. Define $$ S(\alpha) = \sum_{1 \leq n \leq N} \Lambda(n) e^{2 \pi i f(n) \alpha}. $$ I was wondering how does one obtain that $$ \left( \int_0^1 S(\alpha) ...
2
votes
5answers
110 views

Prove the existence or the non-existence of a couple of numbers ($n$,$m$) such that $n^2=m!$ [duplicate]

In recent days, while I was doing exercises on combinatorics, I thought if a number $m!$ could be a perfect square. I proved to demonstrate it through the prime factorization. My attempt: ...
3
votes
3answers
30 views

Prove the sum of any $n$ consecutive numbers is divisible by $n$ (when $n$ is odd).

Let $n \in \mathbb N$ be odd. Prove that the sum of any $n$ consecutive numbers is divisible by $n$. I started out with $s = x + (x + 1) + (x + 2) + … + (x + n) = kx + n.$ What I am interested in ...
2
votes
0answers
25 views

Using gauss's lemma to find $(\frac{n}{p})$ (Legendre Symbol)

Sorry if this ends up being long. So basically, i am trying to understand the proofs of Gauss's lemma for things such as $(\frac{2}{p})$ $(\frac{3}{p})$ etc For $(\frac{2}{p})$ i am given this ...
1
vote
1answer
38 views

Evaluating the Legendre symbol $\left(\frac{5}{p}\right)$ using Gauss's lemma instead of quadratic reciprocity.

So basically, I want to find the Legendre symbol $\left ( \frac{5}{p} \right )$ using Gauss's lemma instead of quadratic reciprocity. The first part of my problem states Write out the first ...
2
votes
1answer
19 views

Order $n^{r-1}$ approximation of product given order $(\frac{1}{n^2})$ approximation of terms

I have that $|a_n - (1+\frac{r}n)| \leq \frac c{n^2}$, for $c$ a constant, and am attempting to show that there exist constants $C < \infty$ and $K > 0$ such that the product $b_n = ...
1
vote
1answer
54 views

Show that $xyxyxy$ is not a perfect power.

If $N=xyxyxy$ where $x$ and $y$ are digits. Show that $N$ cannot be a perfect power, i.e. $N\ne a^b$, where $a$ and $b$ are positive integers and $b>1$. My work $xy|xyxyxy$ and ...
4
votes
1answer
63 views

Solve in positive integers: $5x^2+6x^3=z^3$

Solve in positive integers: $5x^2+6x^3=z^3$. $x^2(6x+5)=z^3$ If $(x,5)=5$, let $x=5k$. So $k^2(6k+1)=\left(\frac{z}{5}\right)^3$, we're left with solving $6n^3+1=m^3$. If $(x,5)=1$, ...
1
vote
2answers
88 views

Understanding a proof showing that for any prime $p$, there are integers $x$ and $y$ such that $p|(x^2+y^2+1)$.

I asked this question a couple days ago: Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $. But I asked it as a guest, and I could not comment on ...
0
votes
1answer
46 views

Let $f(x) = x^2 + x + 41$. Show that $f(n)$ is prime for $0 \le n \le 39$, but $f(40)$ is composite. [duplicate]

$40 \cdot 40 + 40 + 41 = 40(40 + 1) + 41 = 40 \cdot 41 + 41 = 41(40 + 1) = 41^2$, so $f(40)$ is composite. Suppose $f(n) = n^2 + n + 41$ is prime for $0 \le n \le 38$. But $f(n + 1)$ is also prime: ...
0
votes
1answer
26 views

Calculating the Legendre symbols $\left(\frac{295}{401}\right)$ and $\left(\frac{713}{1009}\right)$ using quadratic reciprocity

Evaluate the following Legendre symbols using quadratic reciprocity: $\left(\frac{295}{401}\right)$ $\left(\frac{713}{1009}\right)$ I know that can flip the numbers and reduce because both $401$ ...
0
votes
0answers
20 views

Let $p$ be a prime. Write down the solutions of equation $\frac{1}{x} +\frac{1}{y} =\frac{1}{p}$ [duplicate]

Let $p$ be a prime. Consider the equation $\frac{1}{x} +\frac{1}{y} =\frac{1}{p}$ with $x$ and $y$ positive integers. Write down the complete set of distinct solutions, and prove that your list is ...
-1
votes
0answers
22 views

Quadratic residue dependency on $\bmod 4$ [duplicate]

Let $p$ be an odd prime and let $a$ be a quadratic residue modulo $p$. Write a formal proof showing that $−a$ is also a quadratic residue modulo $p$ if and only if $p ≡ 1 \bmod 4$. I sort of ...
0
votes
1answer
41 views

Establishing the congruences used for the Miller-Rabin primality test

I am supposed to show the following: Let $p>1$ be an integer and write $p−1=2^{k}m$ where $m$ is odd. If for all $a \not\equiv 0 \pmod p$, we have $$\begin{align} && a^m \equiv 1 ...
0
votes
2answers
25 views

Solutions of the Congruence

If $x^{10}\equiv 1\pmod{\!55^2}$, how do I know one must have $x^{10}\equiv 1\pmod{\!5^2}$ and $x^{10}\equiv 1\pmod{\!11^2}$?
-1
votes
4answers
45 views

Last 2 digits of a product

What will be the last two digits of $25^{63} \cdot 63^{25}$? The answer is given as $25$ or $75$. What is the procedure to reach this answer?
5
votes
1answer
38 views

Show that $α$ is a perfect square in the quadratic integers in $\mathbb Q[\sqrt{d}]$

Question: Suppose that $\mathbb Q[\sqrt{d}]$ is a UFD, and $α$ is an integer in $\mathbb Q[\sqrt{d}]$ so that $α$ and $\barα$ have no common factor, but $N(α)$ is a perfect square in $\mathbb Z$. How ...
1
vote
3answers
48 views

Why isn't Euler's theorem working to find the smallest $k$ such that $10^k \equiv 1 \pmod {\!9}$?

$10^k \equiv 1 \pmod {\!9}$ According to Euler's theorem and the Carmichael function, smallest $k$ is $\phi(9) = 6$, but clearly the smallest $k$ is $k=1$. What am I doing wrong?
0
votes
0answers
13 views

Torelli Shanks Algorithm - Repeated Squarring Method

This algorithm is using when you want to find a square root of a number in a given moduli. I can't see the idea behind this algorithm, so can someone explain it in a simple way?
2
votes
1answer
26 views

Why is $\sum_{x=1}^{p-1}\left(\frac{x}{p}\right)=\left(\frac{0}{p}\right)$?

For $p$ an odd prime, why does $$\sum_{x=1}^{p-1}\left(\frac{x}{p}\right)=\left(\frac{0}{p}\right)$$ where $\left(\frac{x}{p}\right)$ is the Legendre symbol. I'm not sure if I have given enough ...
0
votes
1answer
35 views

Given $p$ an odd prime, $x^2\equiv a\pmod{p^2}$ and $(a,p)=1$, how could we know that $(x,p)=1$?

If I have the congruence $$x^2 \equiv a \pmod {p^2}$$ where $p$ is an odd prime and $(a,p)=1$, how could I know that $(x,p)=1$?
0
votes
6answers
41 views

Finding the inverse of a number under a certain modulus

How does one get the inverse of 7 modulo 11? I know the answer is supposed to be 8, but have no idea how to reach or calculate that figure. Likewise, I have the same problem finding the inverse of 3 ...
1
vote
2answers
114 views

Why study Lowest Common Multiple - LCM

What is the most motivating way to introduce LCM of two integers on a first elementary number theory course? I am looking for real life examples of LCM which have an impact. I want to be able to ...