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

learn more… | top users | synonyms (1)

0
votes
0answers
11 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
0answers
19 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 } λ)$, ...
0
votes
4answers
30 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
14 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
37 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
8 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
20 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
29 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
84 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
19 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
1answer
34 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
43 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
vote
1answer
16 views

-a is also a quadratic residue mod p

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.
16
votes
7answers
2k 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 reasoning of ...
1
vote
2answers
25 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
47 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
26 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
64 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
33 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
49 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 ...
0
votes
2answers
35 views

If $ p $ is an odd prime and $ D $ an integer not divisible by $ p $, show that $ x^2 - y^2 \equiv D ~ (\text{mod} ~ p) $ has $ (p - 1) $ solutions.

I am supposed to have proved the following congruence identity: $$ 1^{n} + 2^{n} + \cdots + (p - 1)^{n} \equiv 0 ~ (\text{mod} ~ p). $$ This is apparently meant to help me solve the problem stated in ...
0
votes
0answers
28 views

Are these elementary assertions about quadratic intervals and prime factors true?

Assertion 1: Every quadratic interval is an even number from 2 to infinity. The interval size does not include the interval endpoints, $x^2$ and $(x+1)^2$. Therefore, every interval size is an even ...
0
votes
2answers
32 views

Let $a_n$ be defined inductively by $a_1 = 1, a_2 = 2, a_3 = 3$, and $a_n = a_{n−1} + a_{n−2} + a_{n−3}$ for all $n \ge 4$. Show that $a_n < 2^n$.

Suppose that the numbers $a_n$ are defined inductively by $a_1 = 1, a_2 = 2, a_3 = 3$, and $a_n = a_{n−1} + a_{n−2} + a_{n−3}$ for all $n \geq 4$. Use the Second Principle of Finite Induction to ...
2
votes
1answer
17 views

Show that there exist $k$ and $r$ such that the given sum is divisible by $n$

Let $a_{1},\dots,a_{n}$ be integers. Show that there exist integers $k$ and $r$ such that the sum $$a_{k}+a_{k+1}+\dots+a_{k+r}$$ is divisible by $n$. I am unable to find the necessary way to solve ...
0
votes
0answers
24 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
164 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 ...
1
vote
3answers
55 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
59 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
63 views

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

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
46 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 ...
0
votes
5answers
42 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
32 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 ...
2
votes
5answers
90 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
58 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 ...
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\} = ...
41
votes
2answers
570 views
+50

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 ...
6
votes
3answers
220 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
129 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
48 views

Show the following about m

if $\phi(m)|m-1$ then n is square-free. n a prime or has at least three primes. m prime if is obvious. $\phi(p)|p-1$ since $\phi(p)=p-1$.
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 ...
5
votes
1answer
67 views

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

Momentarily I am studying group of units, and this question seems a bit strange. How could I solve $z^z \equiv z \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
87 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
0answers
37 views

Miller-Rabin: proof the other implication

Let $p > 1$ be an integer and write $p-1=2^kq$ where $q$ is odd. Then for all $a\not\equiv0 \pmod p$ $$a^q = 1 \pmod p$$ or $$a^{2^rq} = -1 \pmod p,\quad 0 \leq r < k.$$ I basically need to ...
5
votes
0answers
156 views

Let $n$ be a positive integer. If $2+2\sqrt{28n^2+1}$ is an integer, then it is a perfect square.

Let $n$ be a positive integer. If $2+2\sqrt{28n^2+1}$ is an integer, then it is a perfect square. My work: $2+2\sqrt{28n^2+1}=m \implies 4(28n^2+1)=m^2-4m+4 \implies m=2k$ $28n^2+1=k^2-2k+1 ...
2
votes
3answers
433 views

Factorial expressed in terms of two other factorials

Can the factorial of $N$ always be expressed by the sum(addition and subtraction) or the product of two other factorials? Do there always exist integer $A$ and $B$ such that $N! = A! + B!$, or $N! = ...
2
votes
0answers
328 views

Fibonacci and Lucas numbers related identities

We know that $H_n$ = $L_n + mF_n$, where $n = 0$ or $n > 0$ is simply relation between Fibonacci sequence and generalized Fibonacci-Lucas sequence. Are there any methods to prove the following ...
2
votes
2answers
27k views

How to get to the formula for the sum of squares of first n numbers? [duplicate]

Possible Duplicate: How do I come up with a function to count a pyramid of apples? Proof that $\sum\limits_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$? Finite Sum of Power? I know that the sum ...