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

learn more… | top users | synonyms (1)

6
votes
3answers
562 views

If $n$ is an even perfect number $ n> 6$ show that the sum of its digits is $\equiv 1 (\bmod 9)$

If $n$ is an even perfect number $ n> 6$ show that the sum of its digits is $\equiv 1 \mod 9$. I know perfect numbers are of the form $(2^{p-1})(2^{p}-1)$. I have a few trials that I have done and ...
2
votes
1answer
262 views

Suppose $p$ is an odd prime. Show that $1^{p-1} +2^{p-1}+ \ldots +(p-1)^{p-1}\equiv -1\pmod p$ [duplicate]

Suppose $p$ is an odd prime. Show that $1^{p-1} +2^{p-1}+ \ldots +(p-1)^{p-1}\equiv -1\pmod p$. I think I need to use Wilson's Theorem on this but I'm not sure how. I believe I am suppose to factor ...
1
vote
2answers
196 views

Does the following inequality hold if and only if $N$ is an odd deficient number?

Let $N \in \mathbb{N}$. (That is, let $N$ be a positive integer.) This is in reference to two of my earlier questions here at MSE: Does the following inequality hold true, in general? Does this ...
0
votes
1answer
73 views

Sequence of natural numbers with special properties

Is there a sequence of natural numbers such that any its subsequence has two terms which are coprime? (Maybe 1, 2, 4, 7, 11, 16, ...?)
3
votes
2answers
303 views

How do you prove the division theorem?

Okay, the division theorem states that there exist natural numbers $a,b,q,r$ such that $b=aq+r$ with the condition that $a>0$ and $0<=r<a$. This is pretty much common sense. Though, how am ...
1
vote
0answers
42 views

Gap:$\;\;L(90,28) := {\{n90 - m28 ∈ N, n, m ∈ N, n < 28\}}$

Which elements of the sets Gap:$$L(90,28) := {\{n90 - m28 ∈ N, n, m ∈ N, n < 28\}}$$ $$$$What would be a quick way to resolve?
2
votes
3answers
191 views

Find the $\gcd(6, 14, 21)$ and express it in the form $6r+14s+21t$ for $r,s, t\in\mathbb{Z}$

Find the $\gcd(6, 14, 21)$ and express it in the form $6r+14s+21t$ for $r,s,t\in \mathbb{Z}$. I'm trying to learn some number theory, which starts with this gcd thing. But I ran into a problem: I ...
4
votes
1answer
143 views

If $p$ and $q=10p+1$ are odd primes, show that $(p/q)=(-1/p)$

$\def\leg#1#2{\left(\frac{#1}{#2}\right)}$ If $p$ and $q=10p+1$ are odd primes, show that $\leg pq=\leg{-1}{p}$ I was trying two cases where $p= 3 \pmod 4$ and $p=1\pmod 4$ If $p\equiv 3 \pmod 4, ...
1
vote
1answer
1k views

What is wrong with my solution of finding remainder of $50^{(51^{52})}$ when divided by 11?

I used the following method using remainder theorem. (I used method from here: Find the remainder of $128^{1000}/153$.) $$\begin{align} (50^{{51}^{52}})/11 & = (50^{2652})/11 \implies \\ ...
2
votes
3answers
73 views

Need help with a number theory question

I can't solve this question I got from a Math Olympiad past paper: Find all integers $a$ such that $\frac{a^2+4}{2a+1}$ is also an integer I know $a$ can be $0$ and $-1$ but I can't ascertain if ...
1
vote
2answers
229 views

what is the remainder when $(17^{3}+19^{3} + 21^{3}+23^{3})$ is divided by 83?

what is the remainder when $(17^{3}+19^{3} + 21^{3}+23^{3})$ is divided by 83? NOTE:$a^{3}+b^{3}=(a+b)(a^2-ab+b^2)$
7
votes
1answer
475 views

Prove that every practical number is either a power of two or a power of two times a non-trivial polygonal number

Prove that every practical number is either a power of two or a power of two times a non-trivial polygonal number, where a number $q$ is practical if and only if every integer less than or equal to ...
2
votes
0answers
68 views

Is my proof correct? (Also formally)

Hello dear community! I just worked on a problem in my discrete mathematics text book and wondered if my approach to a specific exercise is correct. There are no solutions to it, that's the reason I ...
2
votes
0answers
104 views

Lower bound for the length of continued fraction

Define $\mathscr L: \mathbb Q \mapsto \mathbb N$ as the minimal number of terms in the continued fraction of a rational number. Example: the continued fraction of $\frac{5}{8}$ is ...
2
votes
1answer
147 views

show that if $ n-1$ and $n+1$ are both primes and $n>4$, then $\phi(n) \leq n/3$

Show that if $n-1$ and $n+1$ are both primes and $n>4$, then $\phi(n)$ is less than or equal to $n/3$ I tried a few cases If $n=6$, $n-1=5$, and $n+1=7$ then $~\phi(6)=2=n/3$ If $n=12$, ...
-2
votes
2answers
157 views

Show that $1^{p-1} + 2^{p-1} +\ldots + (p-1)^{p-1} \equiv -1 \mod p$

Show that $$1^{p-1} + 2^{p-1} +\ldots + (p-1)^{p-1} \equiv -1 \mod p$$ So, I use Fermat's little theorem, that is if $p$ does not divide $a$, then $a^{p-1}$ is congruent to $1$ (mod $p$). But ...
3
votes
1answer
668 views

Prove $(p-k)!(k-1)!\equiv (-1)^k \text{ mod p }$

Here is a question from my number theory class. Prove $$(p-k)!(k-1)!\equiv (-1)^k \text{ mod p} $$ Help please!
1
vote
1answer
119 views

What three positive integers, upon being multiplied by 3, 5, and 7 respectively and the products divided by 20…

What three positive integers, upon being multiplied by 3, 5, and 7 respectively and the products divided by 20, have remainders in arithmetic progression with common difference 1 and quotients equal ...
1
vote
1answer
41 views

If $ p \equiv 1 \pmod{4}$, prove $((\frac{p-1}{2})!)^2 \equiv -1 \pmod {p}$ where p is prime.

Characteristics: The fields where $ p \equiv 1 \pmod{4}$ has half the number from 1 to $\frac{p-1}{2}$ both in positive and the negative. There can be paired up such that when multiplied together, ...
1
vote
1answer
164 views

Number of Solutions to Diophantine Equation

$(a)$ Let $c < 2\pi$ be a positive real number. Show that there are infinitely many integers $n$ such that the equation $x^2 + y^2 + z^2 = n$ has at least $c\sqrt n$ integer solutions. $(b)$ Find ...
0
votes
1answer
55 views

Find the $x$ and $y$ such that $23771x+19945y=1$ where $|x|$ and $|y|$ are as small as possible

Find the smallest values of $x$ and $y$ such that $|x|$ and $|y|$ would be as small as possible. $$23771x+19945y=1$$ Thank for all the help! I assure you this is not homework!
0
votes
2answers
86 views

Criteria for divisibility by 9

Prove the following criteria for divisibility by 9: If $a = \sum\limits_{i=0}^n(c_i10^i)$, where $c_i \in \mathbb{N}$ and $0 \leq c_i < 10$, then $9|a \iff 9|\sum\limits_{i=1}^nC_i$.
2
votes
1answer
119 views

Prove the Set Contains All Primes Except 2 and 3

Given the sequence $a_n = \sqrt{24n + 1}$. Prove that the set $S = \{a_1, a_2,a_3,...\}$ contains every prime number except $2$ and $3$. Clearly $2,3 \notin S$ since $a_1 = \sqrt{24 + 1} = 5$ and ...
4
votes
1answer
264 views

Number of teeth in gears

I'm building something with an engine that uses gears to reduce/increse movement. The motor has itself some gears, and it's a stepper motor (it gives discrete steps), now the number of steps per ...
0
votes
1answer
888 views

A prime congruent to 3 modulo 4 & sums of squares

Prove: If $p$ is a prime where $p \equiv 3 \pmod{4}$ then $p$ can't be written as the sum of two numbers squared. I attempted by contradiction, supposing that $p=a^2 + b^2$ where $a,b$ are ...
1
vote
0answers
45 views

The cosets of $\mathbb{nZ}$

I'd like to show that the only cosets of $\mathbb{nZ}$ are $\bar a$ for $a=0,1,\dots,n-1$ where $\bar a$ denotes the equivalence class containing $a$. Proof. Any integer $x$ can be written as ...
2
votes
3answers
152 views

Sum of integer parts of different numbers

I have the sum of all these integer parts of different numbers $$ \lfloor 1\rfloor + \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor + \dots + \lfloor \sqrt{15} \rfloor $$ I don't have any idea ...
0
votes
1answer
73 views

Proving that $8\mid n(n^{2}-1)(3n+2)$ [duplicate]

I was trying and could not, as it shows that $$8\mid n(n^{2}-1)(3n+2);\forall n \in \text{N}$$ Induction; looking eight consecutive numbers, what to do and how to do?$$$$Sorry, forgot to add a detail: ...
1
vote
4answers
181 views

$(a^{n},b^{n})=(a,b)^{n}$ and $[a^{n},b^{n}]=[a,b]^{n}$?

How to show that $$(a^{n},b^{n})=(a,b)^{n}$$ and $$[a^{n},b^{n}]=[a,b]^{n}$$ without using modular arithmetic? Seems to have very interesting applications.$$$$Try: $(a^{n},b^{n})=d\Longrightarrow ...
5
votes
2answers
469 views

prove that if $\gcd(a,b)=1$ then $\gcd(a^2, b^2)=1$

Using Bezout's identity I have shown $$(a,b^2)=(b,a^2)=1$$ but what should be the next step? Thanks.
0
votes
1answer
113 views

prove $a,b,c \in\mathbb{Z}$ Show that $gcd(a,b)=1$ and $gcd(a,c)=1$ iff $gcd(a,[b,c])=1$

I have to prove that if $a,b,c,d \in\mathbb{Z}$ Show that $gcd(a,b)=1$ and $gcd(a,c)=1$ iff $gcd(a,[b,c])=1$ I've tried proving the forward direction and im stuck. Proof: Suppose that $gcd(a,b)=1$ ...
4
votes
4answers
130 views

The values of $N$ for which $N(N-101)$ is a perfect square

For how many values of $N$ (integer), $N(N-101)$ is a perfect square number? I started in this way. Let $N(N-101)=a^2$ or $N^2-101N-a^2=0.$ Now if the discriminant of this equation is a ...
0
votes
1answer
97 views

If $a,b,x,y\in\Bbb N$ , and $ax-by=(a,b)$, then $(x,y)=1$

Need to prove an exercise, and for that I need to show that if $$a,b,x,y\in\Bbb N$$ and $$ax-by=(a,b),$$then$$(x,y)=1.$$ How to do this? I have no idea. Please do not use modular arithmetic.
10
votes
2answers
184 views

Is $\lim_{x\rightarrow\infty}\frac{x}{\pi(x)}-\ln(x) =-1$?

$\pi(x)$ is the number of primes not exceeding $x$. The prime number theorem states that $\lim_{x\rightarrow \infty} \frac{\pi(x)}{x/\ln(x)} = 1.$ So I, naïvely, inferred that ...
0
votes
1answer
120 views

Show that if $(a, b) = 1$, $a|c$ and $b|c$, then $(a · b)|c$. [duplicate]

"Show that if $\;(a, b) = 1\;$, $\;a|c\;$ and $\;b|c$, then $(a · b)|c$." $$$$Show: We know that $$x\mid w \;\;\text{and}\;\; y\mid w \Longleftrightarrow \frac{x\cdot y}{(x,y)}\mid w$$So if$$a\mid ...
2
votes
2answers
67 views

Evenness sum grows with slope one-sixth

Let $p_2(n)$ be the highest power of $2$ that divides $n$, i.e., if $2^k$ divides $n$ and no higher power does, then $p_2(n)=k$. Define $\;f_{oe}(k)$ as $+1$ if $k$ is odd, $-1$ if $k$ is even. ...
1
vote
1answer
69 views

A problem of divisibility … If $7\nmid n$, $7\nmid n-1$ and $7\nmid n^{3}+1$ then $7\mid n^{2}+n+1$

$7\nmid n$, $7\nmid n-1\;\;$ and $\;\;7\nmid n^{3}+1$ $\Longrightarrow 7\mid n^{2}+n+1$$$$$Do not quite understand how to do, but do not want to use modular arithmetic, thought of using consecutive ...
2
votes
7answers
448 views

Prove that 360 divides (a-2)(a-1)a.a.(a+1)(a+2)

there's a question which asks to prove that 360 | a2(a2-1)(a2-4) I attempted it in the following manner. a2(a2-1)(a2-4) = (a-2)(a-1)(a)(a+1)(a+2)(a) The first 5 terms represent the product of 5 ...
14
votes
1answer
256 views

Prime pair points slope approaches 1

Take the list of primes, $$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, \ldots$$ and create ordered $(x,y)$ pairs by grouping in sequence, $$(2, 3), (5, 7), (11, 13), ...
7
votes
1answer
142 views

Are there an infinite number of prime quadruples of the form $10n + 1$, $10n + 3$, $10n + 7$, $10n + 9$?

In base 10, any prime number greater than 5 must end with the digits $1$, $3$, $7$, or $9$. For some $n$, $10n + 1$, $10n + 3$, $10n + 7$, $10n + 9$ are all prime: for example, when $n=1$, we have ...
1
vote
1answer
97 views

what are real and imaginary part of this expression

I have $M:=\sqrt{\frac{a\cdot(b+ic)}{de}}$ and all variables $a,b,c,d,e$ are real. Now I am looking for the real and imaginary part of this, but this square root makes it kind of hard.
4
votes
2answers
69 views

diophantine equation $x(x^2-x)+y(y^2-y)=2xy$

OK so I accidentally posted a wrong equation in my previous question and I didn't realize it after it was solved. Hope it helped someone and sorry. This is the more challenging one I wanted to solve.
7
votes
3answers
268 views

integer solutions for $x(x-1)+y(y-1)=xy$

I am in high school right now and I would like to learn how to approach this sort of problems. I think this is called a diophantine eqution. Thanks a bunch This is what I deduces, just so you know ...
2
votes
3answers
417 views

Prove that $44^n-1$ is divisible by $7$ for some $n$

How do I prove that there exists a positive integer n such that $44^n-1$ is divisible by $7$?
2
votes
1answer
44 views

Show $\displaystyle\sum_{k=N_{1}}^{N_{2}-1} k^{s_0}\left(\frac{1}{k^s}-\frac{1}{(k+1)^s}\right) \rightarrow0$ as $N_1, N_2 \rightarrow \infty$

Show $\displaystyle\sum_{k=N_{1}}^{N_{2}-1} k^{s_0}\left(\frac{1}{k^s}-\frac{1}{(k+1)^s}\right) \rightarrow0$ as $N_1, N_2 \rightarrow \infty$, where $s \gt s_0 \ge0$ and $k, N_1, N_2 \in ...
1
vote
0answers
138 views

Existence of prime pairs

Will there always exist a prime pair of the form (p, p+l) for any l where gcd(p,l) = 1 and l is even? Can we always conjecture that there exist infinitely many prime pairs of the form(p, p+l) when ...
2
votes
1answer
76 views

Show that $(a, b) =1$ and $a> b$ then $(a-b,\frac{a^m-b^m}{a-b})=(a-b,m)$

Exercise complicated Number theory Show that $\left(a, b\right) =1$ and $a> b$ then $$\left(a-b,\frac{a^m-b^m}{a-b}\right)=(a-b,m)$$I tried some, but what I got was.$\;\;\;\;$I tried some, but what ...
8
votes
1answer
141 views

For how many $n \in \mathbb{N}$ is $\sqrt{n^2+2379}$ natural?

Here's my attempt at a solution: the expression $\sqrt{n^2+2379}$ is natural iff $$n^2 + 2379 = x^2, \quad \mbox{ for some } x \in \mathbb{N}.$$ Therefore $$(x+n)(x-n)=2379=3 \cdot 13 \cdot 61.$$ I ...
-1
votes
1answer
57 views

exponent mod $n$

What does the term "exponent mod $n$" refer to? I guessed that this refers to the multiplicative order mod n, but it doesn't look like this is the case in what I'm reading right now.
-2
votes
1answer
128 views

Finding the remainder .

How to find the remainder of $\dfrac{7^{8^9}}{1000}$