# Tagged Questions

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

351 views

216 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 .
1k views

### Prove that a primitive root of $p^2$ is also a primitive root of $p^n$ for $n>1$. [duplicate]

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 root ...
3k 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 to ...
453 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 can'...
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 ...
535 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\,$.
25k views

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 ... 1 ... 5answers 5k 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 ... 4answers 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? 6answers 8k views ### Do we have negative prime numbers? Do we have negative prime numbers?$..., -7, -5, -3, -2, ...$6answers 3k 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 ... 1answer 6k 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 $$D(N)=4D\left(\... 3answers 3k views ### GCD of rationals Disclaimer: I'm an engineer, not a mathematician Somebody claimed that \gcd only is applicable for integers, but it seems I'm perfectly able to apply it to rationals also:$$ \gcd\left(\frac{13}{... 4answers 1k 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 ... 5answers 5k 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. ... 2answers 5k views ### Proof: How many digits does a number have?$\lfloor \log_{10} n \rfloor +1$I read recently that you can find the number of digits in a number through the formula$\lfloor \log_{10} n \rfloor +1$What's the logic behind this rather what's the proof? 3answers 214 views ### Showing that$a^n - 1 \mid a^m - 1 \iff n \mid 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 problem ... 5answers 4k views ### Largest integer that can't be represented as a non-negative linear combination of$m, n = mn - m - n$? Why? This seemingly simple question has really stumped me: How do I prove that the largest integer that can't be represented with a non-negative linear combination of the integers$m, n$is$mn - m - n$, ... 7answers 2k views ### If$(a,b)=1$then prove$(a+b, ab)=1$.$(a,b)=1$means$a$and$b$have no prime factors in common$ab$is simply the product of factors of$a$and factors of$b$. Let's say$k\mid a+b$where$k$is some factor of$a$. Then$ka=a+b$and ... 7answers 939 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$p(0)...
There exist $x$ and $y$ such that: $\gcd (a,b) = xa + yb$. Why is this true? What's the reasoning behind it?