# Tag Info

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 kth 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