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

learn more… | top users | synonyms

6
votes
2answers
643 views

Solve the Diophantine equation $ 3x^2 - 2y^2 =1 $

Solve $$ 3x^2 - 2y^2 =1 $$ in $ \mathbb{Z}$. How can we do it? ( All of answers gave me a great help. Thanks a lot kind stackexchangers.)
5
votes
6answers
2k 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. ...
8
votes
1answer
501 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}}$$
8
votes
2answers
470 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
3answers
520 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
2answers
210 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 ...
3
votes
2answers
561 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 = ...
11
votes
0answers
555 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 ...
2
votes
2answers
272 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$, ...
113
votes
6answers
22k 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 ...
24
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 ...
32
votes
7answers
1k views

Bad Fraction Reduction That Actually Works

$$\frac{16}{64}=\frac{1\rlap{/}6}{\rlap{/}64}=\frac{1}{4}$$ This is certainly not a correct technique for reducing fractions to lowest terms, but it happens to work in this case, and I believe there ...
3
votes
2answers
107 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 ...
11
votes
2answers
196 views

Is my shorter expression for $ s_m(n)= 1^m+2^m+3^m+\cdots+(n-1)^m \pmod n$ true?

I'm considering the following sums for natural numbers n,m $$ s_m(n)= \sum_{k=1}^{n-1} k^m =1^m+2^m+3^m+\cdots+(n-1)^m $$ modulo n . Looking at odd n first, I found by analysis of the pattern of ...
16
votes
4answers
3k views

How can I prove that $\gcd(a,b)=1\implies \gcd(a^2,b^2)=1$ without using prime decomposition?

How can I prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$, without using prime decomposition? I should only use definition of gcd, division algorithm, Euclidean algorithm and corollaries to those. ...
9
votes
1answer
5k 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, ...
6
votes
3answers
252 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 ...
0
votes
2answers
295 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).
6
votes
1answer
440 views

A binary quadratic form and an ideal of an order of a quadratic number field

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 + ...
2
votes
2answers
1k views

$x^a - 1$ divides $x^b - 1$ if and only if $a$ divides $b$

Let $x > 1$ and $a$, $b$ be positive integers. I know that $a$ divides $b$ implies that $x^a - 1$ divides $x^b - 1$. If $b = qa$, then $x^b - 1 = (x^a)^q - 1^q = (x^a - 1)((x^a)^{q-1} + \ldots + ...
1
vote
2answers
11k 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 ...
4
votes
1answer
209 views

Number of ordered pairs $(a,b)$ such that $ab \le 3600$

Find number of ordered pairs $(a,b)$ such that $ab\le 3600$ and $a,b \in N$ My attempt : Well, all $a,b \leqslant 60$ are solutions. These 3600 solutions. After that I have no idea how to count the ...
3
votes
4answers
565 views

what is the smallest positive integer in the set $\{24x+60y+2000z \mid x,y,z \in \mathbb{Z}\}$!

I cant understand how to do it please help me. Thanks in advance my question is what is the smallest positive integer in the set $\{24x+60y+2000z \mid x,y,z \in \mathbb{Z}\}$! its options are ...
2
votes
2answers
98 views

Largest modulus for Fermat-type polynomial

Motivated by this question, I wonder: Given $k\in\mathbb N, k\ge2$, what is the largest $m\in\mathbb N$ such that $n^k - n$ is divisible by $m$ for all $n\in\mathbb Z$ ?
1
vote
4answers
197 views

Divisibility and the Fibonacci sequence

While studying the Fibonacci sequence I encountered this problem in the handout, and I can not understand how to do it. Show that if the Fibonacci sequence has a term divisible by a natural number ...
1
vote
1answer
281 views

Discriminant of a binary quadratic form and an order of a quadratic number field

Let $ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$. Let $D = b^2 - 4ac$ be its discriminant. It is easy to see that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$). Conversely ...
1
vote
1answer
312 views

Prove that $n$ is a sum of two squares?

Problem Let $n = p_1.p_2.p_3 \cdots p_k.m^2$, where $p_1, p_2, p_3 \cdots p_k$ are distinct primes. Prove that n is sum of two squares if and only if $p_i$ is either 2 or $p_i \equiv 1 \pmod{4}$ ...
30
votes
2answers
6k views

Yitang Zhang: Prime Gaps

Has anybody read Yitang Zhang's paper on prime gaps? Wired reports "$70$ million" at most, but I was wondering if the number was actually more specific. *EDIT*$^1$: Are there any experts here who ...
9
votes
3answers
626 views

The last two digits of $9^{9^9}$

I tried to calculate the last two digits of $9^{9^9}$ using Euler's Totient theorem, what I got is that it is same as the last two digits of $9^9$. How do I proceed further?
14
votes
3answers
352 views

Prove $n\mid \phi(2^n-1)$

If $2^p-1$ is a prime,(thus $p$ is a prime,too) then $p\mid 2^p-2=\phi(2^p-1).$ But I find $n\mid \phi(2^n-1)$ is always hold, no matter what $n$ is.Such as $4\mid \phi(2^4-1)=8.$ If we denote ...
17
votes
1answer
540 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 ...
16
votes
7answers
3k views

Prime dividing the binomial coefficients

It is quite easy to show that for every prime $p$ and $0<i<p$ we have that $p$ divides the binomial coefficient $\large p\choose i$; one simply notes that in $\large \frac{p!}{i!(p-i)!}$ the ...
14
votes
5answers
633 views

Every integer vector in $\mathbb R^n$ with integer length is part of an orthogonal basis of $\mathbb R^n$

Suppose $\vec x$ is a (non-zero) vector with integer coordinates in $\mathbb R^n$ such that $\|\vec x\| \in \mathbb Z$. Is it true that there is an orthogonal basis of $\mathbb R^n$ containing $\vec ...
9
votes
6answers
3k 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 ...
7
votes
2answers
3k 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 ...
1
vote
2answers
432 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 \\ ...
12
votes
7answers
422 views

How can I find the possible values that $\gcd(a+b,a^2+b^2)$ can take, if $\gcd(a,b)=1$

If $\gcd(a,b)=1$, how can I find the values that $\gcd(a+b,a^2+b^2)$ can possibly take? I can´t find a way to use any of the elemental divisibility and gcd theorems to find them.
3
votes
1answer
347 views

If $|A|=30$ and $|B|=20$, find the number of surjective functions $f:A \to B$.

Let there be: $|A|=n$ and $|B|=m$ if $m>n$ then there are $$m(m-1)\cdots(m-n+1)$$ injective functions, so in this case we have $|A|=30$ and $|B|=20$ that means $m<n$ so there exists a ...
3
votes
3answers
2k views

Prove that $x^{2} \equiv 1 \pmod{2^k}$ has exactly four solution incongruent solutions

Prove that $x^{2} \equiv 1 \pmod{2^k}$ has exactly four solution incongruent solutions. My attempt: We have, $x^2 - 1 = (x - 1) \times (x + 1)$, then $(x - 1)(x + 1) \equiv 0 \pmod{2^k}$ which ...
7
votes
1answer
1k 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
849 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)} ...
6
votes
1answer
1k 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 ...
5
votes
3answers
318 views

Derivation of Pythagorean Triple General Solution Starting Point:

I was reading on proof wiki about the derivation of the general solution to the pythagorean triple diophantine equation: $$ x^2 + y^2 = z^2,. $$ where $x,y,z > 0$ are integers. I came across the ...
5
votes
2answers
978 views

Proof that there are infinitely many primes of the form $4m+3$

I am reading a proof of there are infinitely many primes of the form $4m+3$, but have trouble understanding it. The proof goes like this: Assume there are finitely many primes, and take $p_k$ to be ...
3
votes
2answers
148 views

Number base conversion

How can I convert a number from one base, $b_1 \neq 10$ to another base $b_2 \neq 10$ without going through base $10$ i.e. $b_1\rightarrow 10 \rightarrow b_2$?
10
votes
4answers
2k views

Looking to understand the rationale for money denomination

Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills: $$ s = \sum_{i=1}^k n_i ...
7
votes
13answers
1k views

How can I prove that one of $n$, $n+2$, and $n+4$ must be divisible by three, for any $n\in\mathbb{N}$

Intuitively it's true, but I just can't think of how to say it "properly". Take for example, my answer to the following question: Let $p$ denote an odd prime. It is conjectured that there are ...
7
votes
4answers
1k 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} = ...
6
votes
2answers
92 views

Find all n such that $\phi(n) = n/2$

My idea for the solution is something like this: Since $2 | n$, $n = 2^a p_1^{e1} p_2^{e2} \cdots p_t^{et}$ where $a \geq 1$. Then, $n/2 = \phi(2^a) \phi(p_1^{e1}) \phi(p_2^{e2}) \cdots ...
6
votes
1answer
2k views

If $2^n+1$ is prime, why must $n$ be a power of $2$?

A little bird told me that if $2^n+1$ is prime, then $n$ is a power of $2$. I tend not to trust talking birds, so I'm trying to verify that statement independently. Suppose $n$ is not a power of $2$. ...