Tagged Questions

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

12k 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?
11k 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$$
988 views

43k views

18k 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 ...
3k views

3k views

$n!+1$ being a perfect square

One observes that \begin{equation*} 4!+1 =25=5^{2},~5!+1=121=11^{2} \end{equation*} is a perfect square. Similarly for $n=7$ also we see that $n!+1$ is a perfect square. So one can ask the truth of ...
25k views

Calculating the Modular Multiplicative Inverse without all those strange looking symbols

I am sure all those symbols are really easy for you guys to understand, but I would appreciate it if someone could bring it down to earth for me. How could I do this on a basic calculator? or with a ...
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 ...
60k 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 of ...
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?