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

learn more… | top users | synonyms

17
votes
4answers
6k 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?
32
votes
3answers
6k 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$$
16
votes
4answers
4k 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 ...
11
votes
4answers
2k 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?
10
votes
3answers
1k 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 ...
2
votes
2answers
145 views

Divisibility for 7

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it. Let $n = ...
54
votes
10answers
3k views

Is $1$ a prime number?

Is 1 classified as a prime number? And if so, why? If not, why not?
10
votes
4answers
1k 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
2answers
614 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 ...
16
votes
6answers
10k 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 ...
8
votes
1answer
1k 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 ...
17
votes
3answers
15k 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: ...
41
votes
3answers
2k 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?
23
votes
9answers
6k 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. ...
7
votes
2answers
527 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 + ...
7
votes
6answers
1k views

$-1$ is a quadratic residue modulo $p$ if and only if $p\equiv 1\pmod{4}$

I came across this problem and I believe Lagrange's theorem is the key to its solution. The question is: Let $p$ be an odd prime. Prove that there is some integer $x$ such that $x^2 \equiv −1 ...
2
votes
2answers
22k 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 ...
22
votes
11answers
6k 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 $\frac{9!}{(2!3!4!)} ...
21
votes
6answers
5k 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 ...
13
votes
5answers
3k 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. ...
5
votes
5answers
810 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: ...
1
vote
4answers
3k 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 ...
1
vote
4answers
748 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$ ...
11
votes
2answers
2k views

Multiples of an irrational number forming a dense subset

Say you picked your favorite irrational number $q$ and looking at $S = \{nq: n\in \mathbb{Z} \}$ in $\mathbb{R}$, you chopped off everything but the decimal of $nq$, leaving you with a number in ...
16
votes
5answers
1k 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 ...
6
votes
2answers
2k 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, ...
7
votes
3answers
293 views

Solving simple congruences by hand

When I am faced with a simple linear congruence such as $$9x \equiv 7 \pmod{13}$$ and I am working without any calculating aid handy, I tend to do something like the following: "Notice" that adding ...
2
votes
3answers
1k views

GCD Proof with Multiplication: gcd(ax,bx) = x$\cdot$gcd(a,b)

I was curious as to another method of proof for this: Given $a$, $b$, and $x$ are all natural numbers, $\gcd(ax,bx) = x \cdot \gcd(a,b)$ I'm confident I've found the method using a generic common ...
10
votes
2answers
2k views

$\gcd(b^x - 1, b^y - 1, b^ z- 1,…) = b^{\gcd(x, y, z,…)} -1$ [duplicate]

Possible Duplicate: Number theory proving question? Dear friends, Since $b$, $x$, $y$, $z$, $\ldots$ are integers greater than 1, how can we prove that $$ \gcd (b ^ x - 1, b ^ y - 1, b ^ ...
6
votes
8answers
2k 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? Addendum by LePressentiment on 11/29/2013: (in the interest of ...
4
votes
2answers
1k 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 ...
1
vote
1answer
202 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 ...
107
votes
9answers
4k views

What does $2^x$ really mean when $x$ is not an integer?

We all know that $2^5$ means $2\times 2\times 2\times 2\times 2 = 32$, but what does $2^\pi$ mean? How is it possible to calculate that without using a calculator? I am really curious about this, so ...
29
votes
9answers
7k views

Prove that $\sqrt 2 + \sqrt 3$ is irrational

I have proved in earlier exercises of this book that $\sqrt 2$ and $\sqrt 3$ are irrational. Then, the sum of two irrational numbers is an irrational number. Thus, $\sqrt 2 + \sqrt 3$ is irrational. ...
11
votes
10answers
4k views

What's the proof that the Euler totient function is multiplicative?

That is, why is $\varphi (A\cdot B)=\varphi (A)\cdot \varphi (B)$, if A and B are coprime? It's not just a technical trouble—I can't see why this should be, intuitively: I bellyfeel that its ...
11
votes
6answers
3k views

Show that $11^{n+1}+12^{2n-1}$ is divisible by $133$.

Problem taken from a paper on mathematical induction by Gerardo Con Diaz. Although it doesn't look like anything special, I have spent a considerable amount of time trying to crack this, with no luck. ...
9
votes
2answers
4k views

Help understand the proof of infinitely many primes of the form $4n+3$

This is the proof from the book: Theorem. There are infinitely many primes of the form $4n+3$. Lemma. If $a$ and $b$ are integers, both of the form $4n + 1$, then the product $ab$ is also in ...
6
votes
3answers
647 views

Why (directly!) does every number divide 9, 99, 999, … or 10, 100, 1000, …, or their product?

A curiosity that's been bugging me. More precisely: Given any integers $b\geq 1$ and $n\geq 2$, there exist integers $0\leq k, l\leq b-1$ such that $b$ divides $n^l(n^k - 1)$ exactly. The ...
4
votes
3answers
2k 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?
46
votes
7answers
6k views

Prove every odd integer is the difference of two squares

I know that I should use the definition of an odd integer ($2k+1$), but that's about it. Thanks in advance!
21
votes
5answers
11k views

If $a^2$ divides $b^2$, then $a$ divides $b$

Let $a$ and $b$ be positive integers. Prove that: If $a^2$ divides $b^2$, then $a$ divides $b$. Context: the lecturer wrote this up in my notes without proving it, but I can't seem to figure out ...
3
votes
2answers
171 views

Proving $p\nmid \dbinom{p^rm}{p^r}$ where $p\nmid m$

A question from Advanced Modern Algebra by Joseph J.Rotman. Let $n=(p^r)m $ such that the prime $p\nmid m$.Prove that $p\nmid \dbinom{n}{p^r}$.HINT: Assume otherwise,cross multiply and apply ...
8
votes
3answers
726 views

Prove that a primitive root of $p^2$ is also a primitive root of $p^n$ for $n>1$.

For an odd prime, prove that a primitive root of $p^2$ is also a primitive root of $p^n$ for $n>1$. I have proved the other way round that any primitive root of $p^n$ is also a primitive ...
6
votes
5answers
316 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}$.
4
votes
2answers
11k 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 ...
1
vote
5answers
3k 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?
3
votes
2answers
864 views

If $\gcd(a,b)=1$, then $\gcd(a+b,a^2 -ab+b^2)=1$ or $3$.

Hint: $a^2 -ab +b^2 = (a+b)^2 -3ab.$ I know we can say that there exists an $x,y$ such that $ax + by = 1$. So in this case, $(a+b)x + ((a+b)^2 -3ab)y =1.$ I thought setting $x = (a+b)$ and $y = ...
2
votes
2answers
369 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\,$.
52
votes
7answers
7k 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 ...
8
votes
1answer
4k views

Last non Zero digit of a Factorial

I ran into a cool trick for last non zero digit of a factorial. This is actually a recurrent relation which states that: If $D(N)$ denotes the last non zero digit of factorial, then ...