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

learn more… | top users | synonyms (1)

0
votes
1answer
33 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 ...
2
votes
1answer
13 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
15 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
1answer
27 views

A question on introduction to number theory

Show $2^{36}-1$ is divisible by $9$ and if $2^{36}-1=68a19476735$, then find the value of $a$. Pls help... I think simple algebra can be used. This is a question asked by me on the site ...
1
vote
2answers
37 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
51 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
51 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} \\ ...
5
votes
1answer
65 views

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

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

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

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
21 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 ...
3
votes
4answers
84 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 ...
0
votes
1answer
17 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 too, mod $p$

$p,q\ge 2$ are 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
31 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
39 views

Solutions of the Pell 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 solution? ...
3
votes
0answers
20 views

exponential sum estimate involving 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
101 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
27 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
21 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
26 views

Gauss's Lemma and Quadratic Reciprocity

So basically, i want to find $\left ( \frac{5}{p} \right )$ (legendre symbol) using Gauss's lemma instead of Quadratic Reciprocity. The first part of my problem states Write out the first ...
1
vote
1answer
16 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
48 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
58 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$, ...
0
votes
2answers
76 views

Prove 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 as I asked it as a guest, I could not comment on the ...
0
votes
1answer
45 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
21 views

calculation a Legendre symbol with reciprocity

evaluate the following Legendre symbol using quadratic reciprocity (295/401) (713/1009) I know that can flip the numbers and reduce because both 401 and 1009 are 1 mod p and so on, but I am ...
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
33 views

Miller Rabin, other implication.

I am to show the following: Let $p>1$ be an integer and write $p−1=2^km$ where $m$ is odd. Then for all $a \ \not\equiv 0 \pmod p$ we have $a^m \equiv 1 \pmod p$ or $$a^{2^rm} \equiv -1 \pmod ...
-1
votes
2answers
19 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}$?
-2
votes
0answers
20 views

Show that if $x ≡ 1 (\text{mod } λ)$… [on hold]

So let $λ = (3 + \sqrt{−3})/2 ∈ Q[\sqrt{−3}]$. My question is that how do I show that if $x ≡ 1 (\text{mod } λ)$, then $x^3 ≡ 1 (\text{mod } λ^3)$. Also, how do I show that if $x ≡ −1(\text{mod } λ)$, ...
-1
votes
4answers
44 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?
3
votes
1answer
32 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
43 views

Why is Euler Theorem not working here?

$10^k \equiv 1 \pmod {\!9}$ According to Euler Theorem and Carmichael function, smallest $k$ is $\phi(9) = 6$, but clearly the smallest $k$ is $k=1$. What am I doing wrong?
0
votes
0answers
11 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
21 views

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

For $p$ an odd prime, Why is $$\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
26 views

Simple Number Theory Problem Congruences

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

Inverse of a number within certain modular base

How does one get the inverse of (7) within mod 11 i know the answer is to be 8, but have no idea how to reach or calculate that figure likewise same here again, inverse of (3) within mod 13 is (9) ...
1
vote
2answers
93 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 ...
0
votes
1answer
21 views

Prove that if $ r,p \in \Bbb{N} $, then $ \gcd(r,rp) = r $.

Problem. Prove that if $ r,p \in \Bbb{N} $, then $ \gcd(r,rp) = r $. I tried solving this. If $ \gcd(r,p) = 1 $, then $ \gcd(r,rp) = 1 \times r $. Is that right?
-1
votes
2answers
48 views

$x^2 \equiv a$ mod p, $x^2 \equiv b$ mod p, and $x^2 \equiv ab$ mod p, prove either all three are solvable or exactly one

Let p be an odd prime and a, b ∈ Z with p doesn't divide a and a doesn't divide b. Prove that among the congruence's $x^2 \equiv a$ mod p, $x^2 \equiv b$ mod p, and $x^2 \equiv ab$ mod p, either all ...
-3
votes
3answers
52 views

Is $ n^{2} + 1 $ divisible by $ 7 $? By $ 13 $?

1) Does there exist a positive integer $ n $ such that $ n^{2} + 1 $ is divisible by $ 7 $? Prove assertions. 2) Does there exist a positive integer $ n $ such that $ n^{2} + 1 $ is divisible by $ 13 ...
-1
votes
1answer
28 views

Prove Euclid's lemma does not hold when $p$ is not prime. [on hold]

I understand it is not always true as I can provide an example. Take $11 \times 7 \times 5 $ and divide it by $p = 2 \times 3$. Clearly $p | a$ is not true. But how do I formalize this idea?
-1
votes
2answers
47 views

-a is also a quadratic residue mod p [on hold]

Let p be an odd prime and let a be a quadratic residue modulo p. Prove that −a is also a quadratic residue modulo p if and only if p ≡ 1 mod 4.
24
votes
10answers
4k views

Write 100 as the sum of two positive integers

Write $100$ as the sum of two positive integers, one of them being a multiple of $7$, while the other is a multiple of $11$. Since $100$ is not a big number, I followed the straightforward ...
1
vote
2answers
30 views

Show the number of quadratic residues $a$ modulo $p$ with $1\leq a\leq p-1$ is $(p-1)/2$

Question: When $p$ is an odd prime, show that the number of quadratic residues $a$ modulo $p$ with $1\leq a\leq p-1$ is $(p-1)/2$ Answer: From Euler's criterion $\left(\frac{a}{p}\right)\equiv ...
2
votes
0answers
54 views

Prove $λ$ must divide one of $x$, $y$, or $z$.

Let $λ = (3 + \sqrt{−3})/2 \in \Bbb 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$. ...
0
votes
1answer
27 views

Quadratic congruence prime numbers [on hold]

If $p$ is a prime number... a) show that $x^2 \equiv 1 \pmod{\!p}$ has only the following solutions: $x \equiv 1 \pmod{\!p}$ and $x \equiv -1 \pmod{\!p}$. b) show that $(p-1)! \equiv -1 ...
-2
votes
1answer
66 views

Proof that $\sum_{n=1}^\infty n $ is -1/12 [duplicate]

Why is the sum of all natural numbers $- \frac1{12}$? I need a proof my 14 year-old classmates could understand, with minimal effort on my part ;) I know I can prove it using zeta functions, etc. ...
2
votes
0answers
35 views

Assume that d,u,q are all positive integers. Also, d-u is divisible by q, u-q is divisible by d and q-d is divisible by u.

Assume that d,u,q are all positive integers. Also, d-u is divisible by q, u-q is divisible by d and q-d is divisible by u. What is the solution for $d,u,q$? Am I right to assume that the solution is ...
0
votes
2answers
56 views

Show that $f(a)$ converges after some point

There is a row of 1000 integers. There is a second row below, which is constructed as follows. Under each number $a$ of the first row, there is a positive integer $f(a)$ such that $f (a)$ equals ...