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

learn more… | top users | synonyms

-2
votes
3answers
839 views

How to show that $\gcd(ab,n)=1$?

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.
18
votes
10answers
5k 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 ...
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 ...
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 ...
8
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 ...
9
votes
5answers
973 views

Prove that all even integers $n \neq 2^k$ are expressible as a sum of consecutive positive integers

How do I prove that any even integer $n \neq 2^k$ is expressible as a sum of positive consecutive integers (more than 2 positive consecutive integer)? For example: ...
9
votes
3answers
2k views

How to solve the equation $\phi(n) = k$?

Let $\phi(n) $ is the numbers of number that are relatively prime to n. Then, how could we solve the equation $\phi(n) = k, k > 0?$ For example: $\phi(n) = 8 $ I can use computer program ...
6
votes
2answers
691 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. ...
10
votes
3answers
151 views

Showing that $a^n - 1 | a^m - 1 \iff n | m$

Let $a\ge 2$ be an integer. Show that for positive integers $m,n$, we have $a^n - 1$ divides $a^m - 1$ if and only if $n$ divides $m$. I am having trouble showing this. I've seen a similar ...
8
votes
1answer
531 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}}$$
6
votes
3answers
545 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
255 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
2answers
604 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
574 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
283 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$, ...
120
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 ...
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 ...
10
votes
6answers
798 views

Primes congruent to 1 mod 6

I came across a claim that I found interesting, but can't seem to prove for some reason. I have the feeling it should be easy a prime $p$ can be written in the form $p = a^2 -ab +b^2$ for some ...
15
votes
5answers
678 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 ...
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 ...
11
votes
2answers
202 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 ...
10
votes
7answers
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 ...
9
votes
5answers
414 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 ...
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. ...
15
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, ...
12
votes
7answers
442 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.
6
votes
3answers
268 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
320 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).
13
votes
8answers
2k 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
1answer
449 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 + ...
6
votes
2answers
217 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}$
5
votes
1answer
320 views

Odd perfect number divisors

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

If gcd (a,b)=1 and gcd (a,c)=1, then gcd (a,bc)=1

How do I go about proving this? If gcd (a,b)=1 and gcd (a,c)=1, then gcd (a,bc)=1. I'm very confused with gcd proofs.
4
votes
2answers
484 views

Show for prime numbers of the form $p=4n+1$, $x=(2n)!$ solves the congruence $x^2\equiv-1 \pmod p$. $p$ is therefore not a gaussian prime.

I need to show that for prime numbers of the form $p=4n+1$, $x=(2n)!$ solves the congruence $x^2 \equiv-1\pmod p$. I then need to show this implies p isn't a gaussian prime. I have started to solve ...
3
votes
4answers
666 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
105 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
260 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
296 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
325 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}$ ...
35
votes
6answers
1k views

Is $\sqrt[3]{p+q\sqrt{3}}+\sqrt[3]{p-q\sqrt{3}}=n$, $(p,q,n)\in\mathbb{N} ^3$ solvable?

In this recent answer to this question by Eesu, Vladimir Reshetnikov proved that $$ \begin{equation} \left( 26+15\sqrt{3}\right) ^{1/3}+\left( 26-15\sqrt{3}\right) ^{1/3}=4.\tag{1} \end{equation} $$ ...
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 ...
23
votes
4answers
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 ...
9
votes
3answers
652 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?
18
votes
1answer
568 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 ...
14
votes
3answers
424 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 ...
1
vote
2answers
454 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 \\ ...
9
votes
2answers
2k views

Number of zero digits in factorials

Here is a riddle someone has been asked in a job interview: How many zero digits are there in $100!$? Well, I found the first $24$ quite fast by counting how many times five divides $100!$ ($5$ ...
3
votes
1answer
423 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 ...