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

learn more… | top users | synonyms

0
votes
2answers
394 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
2answers
228 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
2answers
344 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\,$.
2
votes
0answers
152 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
1answer
209 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
628 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
109 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 ...
-3
votes
3answers
867 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
6k 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 ...
25
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 ...
11
votes
2answers
211 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
5answers
1k 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
728 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
157 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
672 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}}$$
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
3answers
568 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
272 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 ...
5
votes
1answer
347 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.
11
votes
0answers
581 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 ...
3
votes
2answers
293 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$, ...
122
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 ...
9
votes
3answers
682 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?
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
839 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
706 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 ...
9
votes
4answers
448 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
6k 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
454 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
278 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 ...
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
458 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
416 views

$n$ divides $\phi(a^n -1)$ where $a, n$ are positive integer. [duplicate]

I need to show that $n$ divides $\phi(a^n -1)$ where $a, n$ are positive integer. could any one give me a hint?
7
votes
4answers
15k 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 ...
6
votes
4answers
205 views

How to prove $ \prod_{d|n} d= n^{\frac{\tau (n)}{2}}$

how to prove: $$ \prod_{d|n} d= n^{\frac{\tau (n)}{2}}$$ $\prod_{d|n} d$ is product of all of distinct positive divisor of $n$, $\tau (n)$ is number (count)of all of positive divisor of $n$
4
votes
7answers
3k 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
496 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
721 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
293 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
2answers
1k 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. Ie. I need to need to find numbers p where x^2 is congruent ...
1
vote
1answer
171 views

Can you determine a formula for this problem?

Given: A list of integers is there.Now there are 2 buckets -bucket A and bucket B.This step is repeated as long as there are numbers left in the list.Integers from start or end of the list are ...
1
vote
1answer
309 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
336 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}$ ...