Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.
6
votes
3answers
1k views
How to use the Extended Euclidean Algorithm manually?
I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
12
votes
3answers
3k views
Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$
For all $a, m, n \in \mathbb{Z}^+$,
$$\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$$
6
votes
1answer
530 views
In how many ways can we colour $n$ baskets with $r$ colours?
In how many ways can we colour $n$ baskets using up to $r$ colours such that no two consecutive baskets have the same colour and the first and the last baskets also have different colours?
For ...
10
votes
4answers
770 views
Highest power of a prime $p$ dividing $N!$
How does one find the highest power of a prime $p$ that divides $N!$ and other related products?
Related question: How many zeros are there at the end of $N!$?
This is being done to reduce ...
12
votes
6answers
6k views
Prove that if $\gcd( a, b ) = 1$ then $\gcd( ac, b ) = \gcd( c, b ) $
I know it might be too easy for you guys here. I'm practicing some problems in the textbook, but this one really drove me crazy.
From $\gcd( a, b ) = 1$, I have $ax + by = 1$, where should I go from ...
37
votes
3answers
1k views
How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes? [duplicate]
Possible Duplicate:
Highest power of a prime $p$ dividing $N!$
How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?
8
votes
3answers
568 views
Motivation behind the definition of GCD and LCM
According to me, I can find the GCD of two integers (say $a$ and $b$) by finding all the common factors of them, and then finding the maximum of all these common factors. This also justifies the ...
34
votes
8answers
2k views
6
votes
3answers
3k views
How to find solutions of linear Diophantine ax + by = c?
I want to find a set of integer solutions of Diophantine equation: $ax + by = c$, and apparently $gcd(a,b)|c$. Then by what formula can I use to find $x$ and $y$ ?
I tried to play around with it:
$x ...
3
votes
2answers
544 views
Order of an Element Modulo $n$ Divides $\phi(n)$
How can I show that the order of an element modulo $n$ divides $\phi(n)$?
I know that if $a$ and $n$ are relatively prime, then the least positive integer $x$ such that $a^x\equiv1\pmod n$ is its ...
20
votes
9answers
3k views
Prove $2^{1/3}$ is irrational.
Please correct any mistakes in this proof and, if you're feeling inclined, please provide a better one where "better" is defined by whatever criteria you prefer.
Assume $2^{1/2}$ is irrational.
...
13
votes
5answers
880 views
How do we prove $n^n \mid m^m \Rightarrow n \mid m$?
I'm not sure I've got this right. When proving $a^n \mid b^n \Rightarrow a \mid b$, can we do this indirectly? In short,
"Suppose $a$ does not divide $b$, this implies that $a^n$ does not divide ...
9
votes
3answers
849 views
Elementary central binomial coefficient estimates
How to prove that $\quad\displaystyle\frac{4^{n}}{\sqrt{4n}}<\binom{2n}{n}<\frac{4^{n}}{\sqrt{3n+1}}\quad$ for all $n$ > 1 ?
Does anyone know any better elementary estimates?
1
vote
1answer
99 views
General method for solving $ax\equiv b\pmod {n}$ without using extended Euclidean algorithm?
Consider the linear congruence equation $$ax\equiv b\pmod { n}.$$ One way to solve it is solving a linear Diophantine equation
$$
ax+ny=b.
$$
I saw somebody solved it by another method somewhere I ...
2
votes
3answers
615 views
GCD Proof with Multiplication
I was curious as to another method of proof for this:
Given $a$, $b$, and $x$ are all natural numbers,
$\gcd(ax,bx)\gcd(a,b) \cdot x$
I'm confident I've found the method using a generic common ...
1
vote
4answers
438 views
How to use fundamental theorem of arithmetic to conclude that $\gcd(a^k,b^n)=1$ for all $k, n \in$ N whenever $a,b \in$ N with $\gcd(a,b)=1$?
How to use fundamental theorem of arithmetic to conclude that $\gcd(a^k,b^n)=1$ for all $k, n \in$ N whenever $a,b \in$ N with $\gcd(a,b)=1$?
Fundamental theorem of arithmetic: Each number $n\geq 2$ ...
43
votes
7answers
5k views
What makes $9$ special?
I don't know if this is a well know fact but I have observed that every number no matter how large that is equally divided by $9$, will equal $9$ if you add all the numbers it is made from until there ...
11
votes
8answers
2k views
Division of Factorials
I have a partition of a positive integer (p). How can I prove that the factorial of p can always be divided by the product of the factorials of the parts?
As a quick example 9!/(2!3!4!) = 1260 (no ...
3
votes
2answers
703 views
Derive a formula to find the number of trailing zeroes in $n!$ [duplicate]
Possible Duplicate:
How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?
I know that I have to find the number of factors of $5$'s, $25$'s, ...
2
votes
0answers
111 views
The homomorphism defined by the system of genus characters
Let $F = ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$.
We say $D = b^2 - 4ac$ is the discriminant of $F$.
It is easy to see that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$).
If ...
2
votes
2answers
2k views
Sum of n consecutive numbers [duplicate]
Possible Duplicate:
Proof for formula for sum of sequence $1+2+3+\ldots+n$?
Is there a shortcut method to working out the sum of n consecutive positive integers?
Firstly, starting at $1 ...
9
votes
5answers
627 views
Prove that all even integers $n \neq 2^k$ are expressible as a sum of consecutive positive integers
How do I prove that any even integer $n \neq 2^k$ is expressible as a sum of positive consecutive integers (more than 2 positive consecutive integer)?
For example:
...
2
votes
4answers
1k views
Proof of Extended Euclidean Algorithm?
There exist x and y such that:
gcd (a,b) = xa + yb
Why is this true? What's the reasoning behind it?
5
votes
6answers
841 views
Why is $\gcd(a,b)=\gcd(b,r)$ when $a = qb + r$?
Given:
$a = qb + r$
Then it holds that $\gcd(a,b)=\gcd(b,r)$. That doesn't sound logical to me. Why is this so?
3
votes
3answers
475 views
A number when successively divided by $9$, $11$ and $13$ leaves remainders $8$, $9$ and $8$ respectively
A number when successively divided by $9$, $11$ and $13$ leaves remainders $8$, $9$ and
$8$ respectively.
The answer is $881$, but how? Any clue about how this is solved?
2
votes
2answers
141 views
Order of numbers modulo $p^2$
Let $p$ be an odd prime and let $g$ be a primitive root modulo $p$. Prove that either $\,p+g\,$ or $\,g\,$ has order $\,p^2-p\,\pmod{p^2}$.
Remark: We know $\,g^{\frac{p-1}{2}}=-1\,$.
2
votes
2answers
200 views
Rewriting repeated integer division with multiplication
In many programming languages, such as C and C++, integer division of positive numbers is defined by simply ignoring the remainder. $5 / 2 == 2$.
In general, is it true of positive integers $a$, $b$, ...
-2
votes
3answers
622 views
How to show that $\gcd(ab,n)=1$?
Let $\gcd(a,n)=\gcd(b,n)=1$. How to show that $\gcd(ab,n)=1$? This is a problem that is an exercise in my course.
17
votes
9answers
3k views
Do infinity and zero really exist?
I'm not going to prove something, this is just a question. From the first day which I went to University until now I had some root problems in some basic mathematical assumptions and concepts. Please ...
10
votes
5answers
1k views
If $n$ is composite, then $n$ divides $(n-1)!$.
I have a proof and need some feedback. It seems really obvious that the statement is true but it is always the obvious ones that are a little trickier to prove. So I would appreciate any feedback. ...
4
votes
0answers
224 views
Bijection between an ideal class group and a set of classes of binary quadratic forms.
Let $F = ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$.
We say $D = b^2 - 4ac$ is the discriminant of $F$.
If $D$ is not a square integer and gcd($a, b, c) = 1$, we say $ax^2 + bxy + ...
3
votes
5answers
473 views
Determine the Set of a Sum of Numbers
I want to determine the set of natural numbers that can be expressed as the sum of some non-negative number of 3s and 5s.
$$S=\{3k+5j∣k,j∈\mathbb{N}∪\{0\}\}$$
I want to check whether that would be:
...
8
votes
2answers
440 views
Basic divisibility fact
I'm trying to prove "the following generalization of Theorem 5 [ Th.5: if $a|bc$ and $(a,b)=1$ then $a | c$ ], which uses the same argument for its proof" (Sierpinski, The Theory of Numbers): if $a$, ...
7
votes
1answer
284 views
Prove that any rational can be expressed in the form $\sum\limits_{k=1}^n{\frac{1}{a_k}}$, $a_k\in\mathbb N^*$
Let $x\in\mathbb{Q}$ with $x>0$.
Prove that we can find $n\in\mathbb{N}^*$ and distinct $a_1,...,a_n \in \mathbb{N}^*$ such that $$x=\sum_{k=1}^n{\frac{1}{a_k}}$$
1
vote
4answers
484 views
How can I prove that all rational numbers are either terminally real or repeating real numbers?
I am trying to figure out how to prove that all rational numbers are either terminally real or repeating real numbers, but I am having a great difficulty in doing so.
Any help will be greatly ...
6
votes
0answers
394 views
Are there unique solutions for $n=\sum_{j=1}^{g(k)} a_j^k$?
Edward Waring, asks whether for every natural number $n$ there exists an associated positive
integer s such that every natural number is the sum of at most s $k$th powers of natural
numbers ...
4
votes
1answer
129 views
Divisibility criteria for $7,11,13,17,19$
A number is divisible by $2$ if it ends in $0,2,4,6,8$. It is divisible by $3$ if sum of ciphers is divisible by $3$. It is divisible by $5$ if it ends $0$ or $5$. These are simple criteria for ...
91
votes
6answers
17k views
Deleting any digit yields a prime… is there a name for this?
My son likes his grilled cheese sandwich cut into various numbers, the number depends on his mood. His mother won't indulge his requests, but I often will. Here is the day he wanted 100:
But ...
23
votes
2answers
1k views
Proof of recursive formula for “fusible numbers”
The set of fusible numbers is a fantastic set of rational numbers defined by a simple rule. The story is well told here but I'll repeat the definitions. It's the formula on slide 17 that I'm trying to ...
17
votes
1answer
451 views
Prove that $\lfloor \sqrt{p} \rfloor + \lfloor \sqrt{2p} \rfloor +…+ \lfloor \sqrt{\frac{p-1}{4}p} \rfloor = \dfrac{p^2 - 1}{12}$
Problem
Prove that $\lfloor \sqrt{p} \rfloor + \lfloor \sqrt{2p} \rfloor +...+ \lfloor \sqrt{\frac{p-1}{4}p} \rfloor = \dfrac{p^2 - 1}{12}$ where $p$ prime such that $p \equiv 1 \pmod{4}$.
I really ...
15
votes
6answers
2k views
prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer
Prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer. For clarity: the denominator is the only part being squared.
My thought process: The numerator is the product of the first n even ...
6
votes
1answer
940 views
If p is an odd prime, prove that $1^2 \times 3^2 \times 5^2 \cdots \times (p-2)^2 \equiv (-1)^{(p+1)/2}\pmod{p}$
I also have to prove this for $$2^2 \times 4^2 \times 6^2 \cdots \times (p-1)^2 \equiv (-1)^{(p+1)/2} \pmod{p}$$
I made some progress so far and got stuck. I said that since p is odd, $(p+1)/2$ is ...
1
vote
2answers
311 views
Euclidean algorithm to find the GCD
I have to find the greatest common divisor of $a=78$ and $b=132$.
I have worked out to
$$\begin{align}
132 & = 78 \times 1 + 54 \\
78 & = 54 \times 1 + 24 \\
54 & = 24 \times 2 + 6 \\
...
7
votes
1answer
635 views
Find the sum of all quadratic residues modulo $p$ where $p \equiv 1 \pmod{4}$
I read one theorem in the book, they said there will be exactly $\dfrac{p-1}{2}$ quadratic residues of $p$. So for each $i$,
$$x^2 \equiv a_i \pmod{p} \text{ where } 1 \leq i \leq p - 1$$
But if we ...
6
votes
4answers
455 views
How do I compute $a^b\,\bmod c$ by hand?
How do I efficiently compute $a^b\,\bmod c$:
When $b$ is huge, for instance $5^{844325}\,\bmod 21$?
When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, ...
5
votes
5answers
250 views
How to solve $100x +19 =0 \pmod{23}$
How to solve $100x +19 =0 \pmod{23}$, which is $100x=-19 \pmod{23}$ ?
In general I want to know how to solve $ax=b \pmod{c}$.
3
votes
2answers
342 views
Base system and divisibility
I have seen the following one. Please give the proof of the observation.
We know that, The difference between the sum of the odd numbered digits (1st, 3rd, 5th...) and the sum of the even numbered ...
2
votes
3answers
154 views
Recovering a number from a remainder list
Consider the following list of equations:
$$\begin{align*}
x \bmod 2 &= 1\\
x \bmod 3 &= 1\\
x \bmod 5 &= 3
\end{align*}$$
How many equations like this do you need to write in order to ...
7
votes
4answers
265 views
$a^2-b^2 = x$ where $a,b,x$ are natural numbers
Suppose that $a^2-b^2 =x$ where $a,b,x$ are natural numbers.
Suppose $x$ is fixed. If there is one $(a,b)$ found, can there be another $(a,b)$?
Also, would there be a way to know how many such ...
7
votes
1answer
2k views
Prove that two any consecutive terms of Fibonacci sequence are relatively prime
Prove that two any consecutive terms of Fibonacci sequence are relatively prime
My attempt:
We have $f_1 = 1, f_2 = 1, f_3 = 2...$. So obviously $\gcd(f1, f2) = 1$.
Suppose that $\gcd(f_n, ...
