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

learn more… | top users | synonyms

19
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?
36
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$$
18
votes
5answers
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 ...
2
votes
2answers
166 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 = ...
55
votes
10answers
3k views

Is $1$ a prime number?

Is 1 classified as a prime number? And if so, why? If not, why not?
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?
5
votes
2answers
632 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 ...
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 ...
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, ...
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?
52
votes
11answers
9k views

Is zero odd or even?

Some books say even numbers start from two but if you consider the number line concept, I think zero should be even because it is in between -1 and +1 (i.e in between 2 odd numbers). What is the real ...
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
536 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
5answers
842 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: ...
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
23k 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!)} ...
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 ...
21
votes
6answers
6k 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. ...
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
758 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$ ...
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
308 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 ^ ...
2
votes
15answers
689 views

How to Prove the divisibility rule for $3$

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large ...
9
votes
4answers
882 views

Induction Proof that $x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1})$

This question is from [Number Theory George E. Andrews 1-1 #3]. Prove that $$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1}).$$ This problem is driving me crazy. $$x^n-y^n = ...
6
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 ...
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 ...
1
vote
1answer
208 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 ...
108
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
5k 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 ...
8
votes
3answers
740 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
3answers
661 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
7k 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!
3
votes
2answers
187 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 ...
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 ...
6
votes
5answers
317 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
12k 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
898 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 = ...