Tag Info

Hot answers tagged

11

Hint: Note that $$n^9 - n = n(n^8 - 1) = n(n-1)(n+1)(n^2+1)(n^4+1)$$ This expression is equal to zero mod $2$ and mod $3$, as $n-1, n, n+1$ are factors. If you can show that at least one of these factors is divisible by $5$ you'll be done, as $2|m, 3|m, 5|m \Rightarrow 30|m$. There are just five cases to consider $n \equiv 0,1,2,3,4 \mod 5$. For example ...


9

Your argument is fine and squares are not a problem. You are not pairing up the divisors, you are just reordering them. Let's walk through your calculation with $n=9$, where the sum of divisors is $1+3+9=13$. We then are asking what the value of $\frac 11 + \frac 13 + \frac 19=S$ is. We multiply by $9$ and get $9S=9+3+1=13, S=\frac{13}9$. The term $3$ ...


9

$$18^{29}\equiv -1\pmod{p}$$ implies that the order of $18$ in $\mathbb{F}_p^*$ is $2\cdot 29=58$ (since $18\not\equiv -1\pmod{p}$), from which $58\mid |\mathbb{F}_p^*|$ follows, i.e.: $$ 58\mid(p-1)\Longleftrightarrow p\equiv 1\pmod{58}.$$ For the second part, given that $p=59$, we have: $$ 18^{29} \equiv ...


9

You can show them that they are adding the digits of multiples of $9$ between $18$ and $90$ and then just list them. $18 \implies 1+8=9$ $27\implies 2+7=9$ $36\implies 3+6=9$ $45\implies 4+5=9$ $54\implies 5+4=9$ $63\implies 6+3=9$ $72\implies 7+2=9$ $81\implies 8+1=9$ $90\implies 9+0=9$ While this approach is not sophisticated, it might be ...


9

For any integer $k$, $3(3k+3)=9(k+1)$ is a multiple of $9$, and one can prove that such a number has digital root $9$.


9

While lab's answer is very elegant, it does rely, in some sense, on luck (as do all elegant answers). Here follows a thorough answer that will let you solve any such problem: First of all, as far as the remainder when divided by $7$ is concerned, there is no difference between $10$ and $3$, so I'm going to work with $$ 3^{10} + 3^{10^2} +3^{10^3} + \cdots + ...


6

$10^3\equiv-1\pmod7$ For integer $n\ge1,10^n=3\cdot\underbrace{33\cdots33}_{n\text{ digits}}+1$ $\implies10^{10^n}=10(10^3)^{\underbrace{33\cdots33}_{n\text{ digits}}}\equiv10\cdot(-1)^{\underbrace{33\cdots33}_{n\text{ digits}}}\equiv10(-1)\equiv4$ for $n\ge1$


6

Hint $\,\ n,m\mid k \!\iff\! nm\mid nk,mk\!\iff\! nm\mid (nk,mk) = (n,m)k\!\iff\! nm/(n,m)\mid k$ Remark $\ $ If we bring to the fore the implicit reflection symmetry we obtain a simpler proof: $\,d\mapsto mn/d\,$ bijects the common divisors of $\,m,n\,$ with the common multiples $\le mn.$ Being order-$\rm\color{#c00}{reversing}$, it maps the ...


6

When $n=1$, our polynomial is $23$. Now evaluate it at $n=1+23$. From "failure," success! Remark: The same basic idea can be used to show that no non-constant polynomial $P(n)$ with integer coefficients can be prime for all natural numbers $n$.


6

I would say $n^2+21n+1=(n+1)^2+19n$, so if $n+1$ has a common factor with $19$, the expression will be divisible by $19$. In fact, $18^2+21\cdot 18+1=703=19\cdot 37$


6

$$\frac{a}{\frac{b}{c}}\ne\frac{\frac{a}{b}}{c} \tag 1$$ The right-hand side of $(1)$ can be written as $$\frac{a}{\frac{b}{c}}=\frac{ac}{b}$$ whereas the left-hand side of $(1)$ can be written as $$\frac{\frac{a}{b}}{c}=\frac{a}{bc}$$ Let's look at an example: Suppose $a=3$, $b=6$, and $c=2$. Then, we have ...


5

As I understand it, you want to know if for any two numbers $m,n \in \mathbb{Z}$ at least one of these four conditions holds. This can be disproved with a counterexample. Consider $(m,n) = (15,21)$. \begin{align} \gcd(15,21) &= 3 \neq 1,\\ \gcd(14,21) &= 7 \neq 1,\\ \gcd(15,20) &= 5 \neq 1,\\ \gcd(14,20) &= 2 \neq 1. \end{align} Hence there ...


5

3 steps of Euclid's algorithm will get you there: $$\begin{align} & \gcd(\underbrace{11\cdots11}_{100},\underbrace{11\cdots11}_{60}) \\ ={}& \gcd(\underbrace{11\cdots11}_{40},\underbrace{11\cdots11}_{60}) \\ ={}& \gcd(\underbrace{11\cdots11}_{40},\underbrace{11\cdots11}_{20}) \\ ={}& ...


5

Anything non-zero divided by itself is 1. End of story.


5

Alternatively, we first prove the following claim. Let $x,y,p,q\in\mathbb{N}$ be such that $\gcd(p,q)=1$ and $x^p=y^q$. Then, there exists $u \in \mathbb{N}$ such that $x=u^q$ and $y=u^p$. Proof: As $\gcd(p,q)=1$, there exist $r,s\in\mathbb{Z}$ such that $pr+qs=1$. Hence, ...


4

$18^{29}\equiv (-1)^{29}=-1\pmod{19}$, so $18^{29}+1\equiv 0$, so $19$ divides your number. $18^{29}=18\cdot(18^2)^{14}\equiv 18\cdot 29^{14}=18\cdot (29^2)^7\equiv 18\cdot 15^7=(18\cdot 15)\cdot(15^2)^3\equiv 34(-11)^3\equiv 34\cdot 26\equiv -1\pmod{59}$, so $59$ divides your number. Using a computer program, one can find that there are only 3 prime ...


3

Yes, that statement is true. In fact, it is true for all $p$ and $q$ integers greater than $1$: they do not need to be distinct or odd primes. The key point is that for positive integers $a$ and $b$, the prime factors of $\operatorname{lcm}(a,b)$ are the same as the prime factors of $ab$, which are also the prime factors of either $a$ or $b$ or both. Let me ...


3

This doesn’t work, I’m afraid. The extended Euclidean algorithm gives you some pair of integers $x$ and $y$ such that $ax+cy=\gcd(a,c)$, but there’s no guarantee that $bx+cy=\gcd(b,c)$ for that same pair of integers. HINT: Since $a\mid b$, you know that for every $d$, if $d\mid a$, then $d\mid b$.


3

That division you give seems to be division for integers. If $b > a$ it turns into $$ a = 0 \cdot b + a $$ Thus having the result $q=a/b = 0$ and rest $r=a \bmod b = a$.


3

You almost got it. Since $d\mid b$ and $d\mid c$, $d=1$. Then, $b=av-c$. So $a$ and $c$ are coprime, too.


3

Yes. This is known as Fermat's little theorem. This states $$a^p \equiv a \mod p$$ This gives $a^p-a \equiv 0 \mod p$, or $p \mid a^p-a$. There is a generalisation known as the Euler-Fermat theorem. This states $$a^{\varphi(m)} \equiv 1 \mod m$$ iff $\gcd(a,m)=1$. Because $\varphi(9)=6$, we have $$a^{6} \equiv 1 \mod 9$$ iff $\gcd(a,9)=1$.


3

In $\frac{a/b}{c}=\frac{a}{bc}$, we divide $a$ by $b$, then divide the result by $c$. In $\frac{a}{b/c}=\frac{ac}{b}$, we divide $b$ by $c$, then divide $a$ by the result. The two mean different things.


3

Let $\omega = e^{\frac{i\pi}{3}}$, then $\omega^2 - \omega + 1 = 0$. If there is a $n$ such that $x^2 - x + 1 $ divides $P_n(x) = x^{n+1} + x^n + 1$, then $$ 0 = P_n(\omega) = \omega^n(\omega+1)+1.$$ $$ \omega^n(\omega+1) = -1.$$ $\omega+1 = \sqrt{3}e^{\frac{i\pi}{6}}$ is a vector of length $\sqrt{3}$. After a rotation it becomes $-1$, a vector of length ...


3

It sounds like you've found that the largest integer $x$ such that $a\equiv b\bmod x$ is $x=a-b$ (having assumed, WLOG, that $a\geq b$). That's because, by definition, $$a\equiv b\bmod x\iff x\mid a-b$$ and the largest divisor of any integer is itself.


3

If $n$ is even and $\ge 4$, and not divisible by $3$, use $n(n-1)(n-3)$. If $n$ is even and divisible by $3$, use $(n-1)(n-2)(n-3)$.


3

Hint $\ f_1(r) = 0 = f_2(r)\,\Rightarrow \gcd(f_1,f_2)(r) = 0\,$ by $\,\gcd(f_1,f_2) = h_1 f_1\! + h_2 f_2\,$ by Bezout.


2

You notice the fact about the gcd's (i.e., mdc's) of the numbers $a_i$ and $c_i$. The key here is to notice that $b$ and $d$ can also be assumed relatively prime (if they have gcd equal to $k$, then take the $k$th root of both sides of $a^b = c^d$ to reduce to the case where the exponents are relatively prime.) Now the key fact is known as Euler's Lemma: ...


2

Let us look case by case Either $b$ divides $d$ ( or $d$ divides $b$, it is similar ) then we get $a_i=\frac{d}{b}c_i$. Thus your claim is satisfied as for vector $v=[c_1,c_2..c_n]$ your vector $a=\frac{d}{b}v$ and $c=v$. $b$ and $d$ are co-primes then $a_i=k_id$ and $c_i=k_ib$ ( here $k_i$ are integers ). Again your claim is satisfied as for vector ...


2

Let $q$ be any positive integer, and for $n \ge 0$ set $$ U_{n} = \frac{q^{n} -1}{q-1}. $$ You want to prove that for $m, n \ge 0$ $$\tag{gcd's} \gcd(U_{n}, U_{m}) = U_{\gcd(n, m)}. $$ This follows from the elementary fact that $U_{n}$ divided by $U_{m}$, with $m > 0$, leaves as a remainder $U_{r}$, where $r$ is the remainder of the division of $n$ by ...


2

Hint: For any $a,b$ real numbers: $min(a,b)+max(a,b)=a+b$. Now, if we have $a=a_1^{p_1}*a_2^{p_2}...$ and similarly with $b$, if you use the equation I just mentioned for all $p_i$, you will get, that $gcd(a,b)*lcm(a,b)=a*b$.



Only top voted, non community-wiki answers of a minimum length are eligible