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

learn more… | top users | synonyms (1)

12
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. ...
8
votes
3answers
806 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 ...
5
votes
1answer
115 views

$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1$, or $p$

Let $p$ be prime number ($p\gt2$) and $a,b\in\mathbb Z$ ,$a+b\neq0$ ,$\gcd(a,b)=1$ how to prove that $$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1~~\text{or}~~ p$$ Thanks in advance .
4
votes
4answers
1k views

Not understanding Simple Modulus Congruency

Hi this is my first time posting on here... so please bear with me :P I was just wondering how I can solve something like this: $$25x ≡ 3 \pmod{109}.$$ If someone can give a break down on how to do ...
6
votes
3answers
697 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 ...
5
votes
5answers
281 views

Proving that $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m,n )} - 1$

Somewhere on Stack Exchange I saw the equation $$\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1.$$ I had never seen this before, so I started trying to prove it. Without success... Can anyone explain me (so ...
3
votes
2answers
1k 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
473 views

Prove that if $a^n\mid b^n$ then $a\mid b$

Prove that if $ a^n \mid b^n $ then $a\mid b$ (without use of GCD and factorization theorem).
1
vote
5answers
4k 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
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?
19
votes
5answers
2k views

Number of consecutive zeros at the end of $11^{100} - 1$.

How many consecutive zeros are there at the end of $11^{100} - 1$? Attempt Trial and error on Wolfram Alpha shows using modulus shows that there are 4 zeros (edit: 3 zeros, not 4). Otherwise, I have ...
13
votes
4answers
709 views

“If $1/a + 1/b = 1 /c$ where $a, b, c$ are positive integers with no common factor, $(a + b)$ is the square of an integer”

If $1/a + 1/b = 1 /c$ where $a, b, c$ are positive integers with no common factor, $(a + b)$ is the square of an integer. I found this question in RMO 1992 paper ! Can anyone help me to prove ...
23
votes
6answers
13k 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 ...
9
votes
2answers
226 views

Let $p$ be prime and $(\frac{-3}p)=1$. Prove that $p$ is of the form $p=a^2+3b^2$

Let $p$ be prime and $(\frac{-3}p)=1$, where $(\frac{-3}p)$ is Legendre symbol. Prove that $p$ is of the form $p=a^2+3b^2$ My progress: $(\frac{-3}p)=1 \Rightarrow$ ...
9
votes
5answers
5k views

Prove that $(n-1)! \equiv -1 \pmod{n}$ iff $n$ is prime

How can I show that $(n-1)!$ is congruent to $-1 \pmod{n}$ if and only if $n$ is prime? Thanks.
15
votes
4answers
2k views

$n!+1$ being a perfect square

One observes that $4!+1 =25=5^{2}$, $5!+1=121=11^{2}$ 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 this question: Is $n!+1$ a ...
10
votes
4answers
71k views

What five odd integers have a sum of $30$?

I've been asked the following question: What five odd integers from the set $\{1, 3, 5, 7, 9, 11, 13, 15\}$ that when summed together equals to $30$? Note that any integer can be used more than ...
9
votes
2answers
503 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$, ...
6
votes
5answers
336 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}$.
6
votes
6answers
571 views

How do I show that the sum $(a+\frac12)^n+(b+\frac12)^n$ is an integer for only finitely many $n$?

Show that if $a$ and $b$ are positive integers, then $$\left(a +\frac12\right)^n + \left(b+\frac{1}{2}\right)^n$$is an integer for only finitely many positive integers $n$. I tried hard but ...
4
votes
2answers
13k 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 ...
7
votes
2answers
267 views

Compositeness of $n^4+4^n$ [duplicate]

My coach said that for all positive integers $n$, $n^4+4^n$ is never a prime number. So we memorized this for future use in math competition. But I don't understand why is it?
2
votes
2answers
399 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\,$.
6
votes
3answers
1k views

Concise proof that every common divisor divides GCD without Bezout's identity?

In the integers, it follows almost immediately from the division theorem and the fact that $a | x,y \implies a | ux + vy$ for any $u, v \in \mathbb{Z}$ that the least common multiple of $a$ and $b$ ...
6
votes
3answers
823 views

Field with natural numbers

To make sure that we are talking about the same, I would like to post the relevant definitions I know first. Definitions: A pair $(G, +)$ where $G$ is a set and $+: G \times G \rightarrow G$ is ...
4
votes
5answers
4k views

Simple Proof by induction: “9 divides $n^3 + (n+1)^3 + (n+2)^3$”

I'm trying to prove using induction that 9 divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a non-negative integer. So far, I have: Base case: P(1) = (1) + (8) + (27) = 36, 36 can be divided by 9 ...
1
vote
6answers
224 views

Solving a Linear Congruence

I've been trying to solve the following linear congruence with not much success: 19 congruent to $19\equiv 21x\text{ (mod }26)$ If anyone could point me to the solution i'd be grateful, thanks in ...
8
votes
1answer
5k 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 ...
7
votes
7answers
3k views

Easiest and most complex proof of $\gcd (a,b) \times \operatorname{lcm} (a,b) =ab.$

I'm looking for an understandable proof of this theorem, and also a complex one involving beautiful math techniques such as analytic number theory, or something else. I hope you can help me on that. ...
5
votes
1answer
1k views

Probability that two random numbers are coprime

This is a really natural question for which I know a stunning solution. So I admit I have a solution, however I would like to see if anybody will come up with something different. The question is ...
9
votes
4answers
2k views

Proof of irrationality of square roots without the fundamental theorem of arithmetic

Here is an elementary proof (adapted from Hardy's A Course of Pure Mathematics) that for any integer $k$, $\sqrt{k}$ is either irrational or integral. Suppose $\sqrt{k}$ is rational, $\sqrt{k} = ...
3
votes
7answers
575 views

Test for an Integer Solution

This came up an a training piece for the Putnam Competition and also in Ireland and Rosen. The question posed was basically: Let $p(x)$ be a polynomial with integer coefficients satisfying that ...
6
votes
2answers
1k views

On the factorial equations $A! B! =C!$ and $A!B!C! = D!$

I was playing around with hypergeometric probabilities when I wound myself calculating the binomial coefficient $\binom{10}{3}$. I used the definition, and calculating in my head, I simplified to this ...
15
votes
8answers
3k views

Prove that none of $\{11, 111, 1111,\dots \}$ is the perfect square of an integer

Please help me with solving this : prove that none of $\{11, 111, 1111 \ldots \}$ is the square of any $x\in\mathbb{Z}$ (that is, there is no $x\in\mathbb{Z}$ such that $x^2\in\{11, 111, 1111, ...
6
votes
3answers
320 views

bijection between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ [duplicate]

I understand that both $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ are of the same cardinality by the Shroeder-Bernstein theorem, meaning there exists at least one bijection between them. But I ...
6
votes
4answers
1k views

Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them

Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them. Let $a$ be the primitive root then I know other primitive roots will be among $\{a,a^2,a^3 \cdots\cdots a^{\phi(n)} ...
5
votes
1answer
406 views

Can an odd perfect number be divisible by $105$?

I have a tough one today. Show that if $n$ is an odd perfect number, then not all of $3$, $5$, and $7$ are divisors of $n$. Any and all help is appreciated. Thanks very much.
6
votes
2answers
247 views

Closed form for $(p-n)!\pmod{p}$ where $p$ is prime

Does $(p-n)!\pmod{p}$ have a closed form for any $n>2$ when $p$ is prime? $(p-0)!=0 \pmod{p}$ $(p-1)!=-1\pmod{p}$ $(p-2)!=1\pmod{p}$
2
votes
0answers
155 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
5answers
2k views

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$, where $n=0,1,2, \dots$
1
vote
2answers
2k views

Determine all primes p for which 5 is a quadratic residue modulo p

I need to determine all primes $p$ for which $5$ is a quadratic residue modulo p. I think I'll need to use quadratic recprocity laws to do this, i.e., I need to need to find numbers $p$ where ...
2
votes
1answer
287 views

$a|\phi(a^n-1)$ for $a,n$ such that $(a,n)=1$?

we need to find out which of the following are true $\phi(n)|n$ $n|\phi(a^n-1)$ for all $a$ and $n$ $n|\phi(a^n-1)$ for $a,n$ such that $(a,n)=1$ $a|\phi(a^n-1)$ for $a,n$ such that $(a,n)=1$ ...
1
vote
6answers
720 views

$ p^{\frac1n} $ is irrational if $p $ is prime and $n>1$ [closed]

How can we prove that $ p^{\frac1n} $ is irrational if $p $ is prime and $n>1$?
1
vote
4answers
116 views

Find $ord_m b^2$ if $ord_m a = 10$ and $ab\equiv 1\pmod m$

If $ab \equiv 1 \pmod {m}$ and if $ord_ma=10$, find $ord_mb^2$. Could somebody give me a hint? What I know is that $ab \equiv 1 \pmod {m}$ can be used when finding the multiplicative inverse. Would ...
-2
votes
3answers
1k views

How to show that $\gcd(ab,n)=1$? [on hold]

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.
20
votes
10answers
7k 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 ...
45
votes
10answers
3k views

Given real numbers: define integers?

I have only a basic understanding of mathematics, and I was wondering and could not find a satisfying answer to the following: Integer numbers are just special cases (a subset) of real numbers. ...
27
votes
5answers
2k views

Why is the last digit of $n^5$ equal to the last digit of $n$?

I was wondering why the last digit of $n^5$ is that of $n$? What's the proof and logic behind the statement? I have no idea where to start. Can someone please provide a simple proof or some general ...
27
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 ...