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

learn more… | top users | synonyms

3
votes
2answers
905 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
378 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\,$.
1
vote
6answers
162 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 ...
52
votes
7answers
7k views

What makes $9$ special?

I don't know if this is a well know fact but I have observed that every number no matter how large that is equally divided by $9$, will equal $9$ if you add all the numbers it is made from until there ...
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 ...
19
votes
5answers
1k 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 ...
12
votes
4answers
625 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 ...
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 ...
7
votes
6answers
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. ...
3
votes
7answers
489 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 ...
14
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, ...
9
votes
2answers
491 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$, ...
1
vote
2answers
429 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
238 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
154 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 ...
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
251 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
671 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
112 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
956 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.
19
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 ...
26
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 ...
26
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 ...
11
votes
2answers
221 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
1answer
7k 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, ...
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
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.
11
votes
3answers
437 views

Is there a direct, elementary proof of $n = \sum_{k|n} \phi(k)$?

If $k$ is a positive natural number then $\phi(k)$ denotes the number of natural numbers less than $k$ which are prime to $k$. I have seen proofs that $n = \sum_{k|n} \phi(k)$ which basically ...
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
169 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$ ...
6
votes
2answers
871 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.)
10
votes
3answers
162 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
724 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
6answers
566 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 ...
14
votes
4answers
453 views

Why do repunit primes have only a prime number of consecutive $1$s?

Repunit primes are primes of the form $\frac{10^n - 1}{9} = 1111\dots11 \space (n-1 \space ones)$. Each repunit prime is denoted by $R_i$, where $i$ is the number of consecutive $1$s it has. So far, ...
10
votes
4answers
330 views

Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$

I can't crack this one. Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$ (the only constraint is that $a,b,c,z \in \mathbb{Z}$).
5
votes
2answers
294 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
364 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
5answers
1k 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$
12
votes
0answers
602 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 ...
5
votes
6answers
203 views

How to solve the diophantine equation $8x + 13y = 1571$

I'm having trouble solving the following diophantine equation: $8x + 13y = 1571$ For all the other examples I've worked through I've been able to use the euclidean algorithm and the solution ...
3
votes
2answers
305 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$, ...
1
vote
2answers
90 views

If $\operatorname{ord}_ma=10$, find $\operatorname{ord}_ma^6$

If $\operatorname{ord}_ma=10$, find $\operatorname{ord}_ma^6$. Justify you're answer. I'm not sure what I should say for my answer to be justified. However, I expect $\operatorname{ord}_ma^6=5$, ...
125
votes
6answers
23k 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 ...
19
votes
5answers
36k views

How to find the inverse modulo m?

For example: $$7x \equiv 1 \pmod{31} $$ In this example, the modular inverse of $7$ with respect to $31$ is $9$. How can we find out that $9$? What are the steps that I need to do? Update If I have ...
9
votes
4answers
746 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?
33
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
932 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 ...