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

learn more… | top users | synonyms (1)

0
votes
0answers
9 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 ...
0
votes
1answer
19 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 ...
0
votes
0answers
7 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 the product $b_n = \prod_{i=1}^n a_i$ can be approximated as $$|b_n - Kn^r| \leq C n^{r-1}$$ ...
1
vote
1answer
45 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 ...
3
votes
1answer
34 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
1answer
52 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
44 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
17 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
18 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
0answers
15 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 \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 } λ)$…

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
39 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?
2
votes
0answers
16 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
39 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
5answers
30 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
85 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
20 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
42 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
50 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
2answers
45 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.
21
votes
9answers
3k 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 ...
0
votes
3answers
57 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 ...
0
votes
5answers
47 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
6answers
99 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
60 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 ...
2
votes
0answers
35 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 ...
3
votes
2answers
84 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 ...
3
votes
0answers
38 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\} = ...
15
votes
2answers
689 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 ...
0
votes
1answer
63 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 ...
41
votes
3answers
592 views

Finding triplets $(a,b,c)$ such that $\sqrt{abc}\in\mathbb N$ divides $(a-1)(b-1)(c-1)$

When I was playing with numbers, I found that there are many triplets of three positive integers $(a,b,c)$ such that $\color{red}{2\le} a\le b\le c$ $\sqrt{abc}\in\mathbb N$ $\sqrt{abc}$ divides ...
7
votes
0answers
102 views

A problem about $e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$

Let $\alpha_i\in [0,1),\; i\in \{1,\cdots,N\}$ for some positive integer $N$, such that $$e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$$ and if for any non-empty proper subset ...
6
votes
3answers
221 views

I finally understand simple congruences. Now how to solve a quadratic congruence?

Now that I have plain old congruences, $19x\equiv 4 \pmod {141}$ for example, I am trying to wrap my brain around quadratic ones. My textbook shows how to tackle the aforementioned congruences, but ...
5
votes
2answers
130 views

Proving that the sum and difference of two squares (not equal to zero) can't both be squares.

I have the following task: Prove that the sum and the difference of two squares (not equal to zero) can't both be squares. For the sum, I thought about Pythagorean triples: $x^2+y^2=z^2$ works ...
1
vote
2answers
53 views

If $\phi(n) |n-1$, then $n$ is square-free or has at least three prime factors

If $\phi(n) |n-1$ then $n$ is square-free. Show also that $n$ is either a prime or has at least three prime factors. $n$ prime if is obvious: $\phi(p)|p-1$ since $\phi(p)=p-1$.
-3
votes
2answers
34 views

How do you show that$ ∏j ≡1 $(mod p) where j is $1 \le j\le p-1$ and $\frac{j}{p}=1$ [closed]

Also, $P$ is a prime of the form $4k+3$ and $k$ is an element of natural numbers including $0$.($\frac{j}{p}$) denotes a legendre symbol.
22
votes
2answers
2k views

What is the next perfect square of the form 14444… in decimal notation?

We know that $12^2 = 144$ and that $38^2 = 1444$. Are there any other perfect squares in the form of $\frac{13}{9} (10^n - 1) + 1$ (i.e. $1$ followed by $n$ $4$'s), and how would we prove it?
2
votes
1answer
45 views

$g^q-q$ and $g^q-gq$ are primitive roots modulo $q^2$

Let $g$ be a primitive root modulo an odd prime $q$. Then, both $g^q-q$ and $g^q-gq$ are primitive roots modulo $q^2$. I read this question somewhere and the first thing that came to my mind as a ...
1
vote
1answer
42 views

Proving $\frac{p-1}{2}$ is a primitive root modulo $p$ if and only if $2(-1)^{(p-1)/2}$ is a primitive root modulo $p$

Let $p$ be an odd prime. Prove that $\frac{p-1}{2}$ is a primitive root modulo $p$ if and only if $2(-1)^{(p-1)/2}$ is a primitive root modulo $p$. I was thinking that since $\frac{p-1}{2}$ is a ...
6
votes
2answers
103 views

Solving $x^x \equiv x \pmod{17}$.

Momentarily I am studying group of units, and this question seems a bit strange. How could I solve $x^x \equiv x \pmod{17}$?
2
votes
1answer
63 views

$\phi(m)/m$ is minimal

I am working on a number theory exam and this question seems quite interesting. How do I really approach it? Determine the element $n_k$ of the set {$m \in N: w(m)=k$} for which $\phi(m)/m$ is ...
1
vote
3answers
89 views

Find j,k such that $2^a + 3 = 7^b$

Find all $a,b$ such that $2^a + 3 = 7^b$. I think that the only solution is $a=2$. Because of the exponential growth of $2$ and $7$. But I am not that sure.
0
votes
2answers
51 views

If $a=b+c$ then $(a,b)=(a,c)=(b,c)$

If $a=b+c$ then $(a,b)=(a,c)=(b,c)$ I was thinking of writing the Euclidean algorithm \begin{align*}a &= b\cdot 1+c\\ b &= c\cdot (-1) + (b+c)\\ c &= a \cdot 1 + ...
1
vote
1answer
56 views

Restating a floor function as a finite sum

It seems to me that a floor function can be expressed as a finite sum that is open to the Möbius function. Does it follow for all nonnegative integers $a$ that: ...
4
votes
2answers
195 views

Evaluation of the sum $\sum_{i=1}^{\lfloor na \rfloor} \left \lfloor ia \right \rfloor $

Let $a$ be a positive proper fraction and $n$ is any integer then evaluate the following sum, $$\sum_{i=1}^{\left \lfloor na \right \rfloor\atop} \left \lfloor ia \right \rfloor $$ I think that ...
11
votes
1answer
242 views

Is the equation $\phi(\pi(\phi^\pi)) = 1$ true? And if so, how?

$\phi(\pi(\phi^\pi)) = 1$ I saw it on an expired flier for a lecture at the university. I don't know what $\phi$ is, so I tried asking Wolfram Alpha to solve $x \pi x^\pi = 1$ and it gave me a bunch ...