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

learn more… | top users | synonyms (1)

3
votes
4answers
956 views

what is the smallest positive integer in the set $\{24x+60y+2000z \mid x,y,z \in \mathbb{Z}\}$!

I cant understand how to do it please help me. Thanks in advance my question is what is the smallest positive integer in the set $\{24x+60y+2000z \mid x,y,z \in \mathbb{Z}\}$! its options are ...
1
vote
1answer
51 views

Prove $[a]_n$ has a unique representative $r$ where $0\leq r<n$

Prove each congruence class $[a]_n$ in $\mathbb{Z_n}$ has a unique representative $r$ such that $0\leq r<n$. My proof. Assume to the contrary that $[a]_n$ does not have a unique $r$. That is let ...
1
vote
2answers
72 views

Proof read from “A problem seminar”

May you help me judging the correctness of my proof?: Show that the if $a$ and $b$ are positive integers, then $$\left(a+\frac{1}{2}\right)^n+\left(b+\frac{1}{2}\right)^n$$ is integer for only ...
1
vote
0answers
53 views

How to compute the number of solutions of primitive modulo equation?

Consider the equation: $$x^p \equiv a \pmod{M}$$ where $p, a$ and $M$ is given. Is there a quick way to compute the number of solutions to the above equation? I'm so rusty in Number Theory now, so ...
3
votes
0answers
91 views

Positive integers $n$ so that $n^2$ divides $2^n+1$. [duplicate]

Find all positive integers $n$ for which $n^2$ divides $2^n+1$.
1
vote
0answers
102 views

Continued fraction of $\gamma+1$ using recursion

Number $\gamma,$ the Euler-Mascheroni constant, is defined as the value of $$\gamma = \lim_{n\to\infty} \sum_{k=1}^n \frac{1}{k} - \ln(n).$$ We know that $$\lim_{n\to\infty} ...
6
votes
5answers
328 views

Is Collatz' conjecture the only stable solution of its type?

The Collatz Conjecture is well known with the sequence $$f(n) = \begin{cases} n/2 &;\text{if } n \equiv 0 \pmod{2}\\ k\,n+1 &; \text{if } n\equiv 1 \pmod{2} \end{cases}$$ and $k=3$; the ...
3
votes
2answers
87 views

Is this bijection between subsets of $\mathbb{Z}$ right?

I was trying to prove the following: For some fixed $n \in \mathbb{N}$ define the following set of integers $S_4(n) = \{k \in \mathbb{Z} : k = n+j, j \in \{0,1,2,3\}\subset \mathbb{Z}\}$, then if $A = ...
7
votes
2answers
375 views

Given three integers in $\{0,\ldots,100\}$ which sum up to $100$. What is the probabilty that two of them are the same?

We pick $3$ numbers (one by one) from set $\{0,1,...,100\}$. What is probabilty that two numbers are the same if sum of those $3$ numbers is $100$? My solution: Which two are the same we can pick in ...
0
votes
2answers
60 views

Can't remember a number theory problem (from Hofstadter?)

I'm thinking of a problem in number theory in which one applies a recurrence that's something like doubling $n$ if it's even and taking it over $3$ if it's odd...but with some ceilings or additions ...
3
votes
1answer
57 views

Proving that $\left\lfloor\frac{n m -1}{m-1}\right\rfloor, n>0, m>0$ yields only natural numbers that is not a multiple of $m$

Let $A(n,m)$ denote a set such that: $$A(n,m) = \{k\in\mathbb{N}_{>0} \mid (j \in \mathbb{N}) \wedge (k \neq jm)\} \implies$$ $$A(n,2) = \{1,3,5,7,\dots\}$$ $$A(n,4) = \{1,2,3,5,6,7,9,\dots\}$$ ...
5
votes
2answers
186 views

Pythagorean Quadruples:

Consider the set of integers $x_1, x_2, x_3, x_4$ Such that: $$x_1^2 + x_2^2 + x_3^2 = x_4^2$$ How does one compute all the solutions to this system? I have the following method in place for ...
5
votes
2answers
313 views

$n\text{ odd}\implies n^2=8k+1$ for some $k\in \mathbb{Z}$

So this girl tells me "Did you know that if $n$ is odd, then $n^2=8k+1$ for some $k\in \mathbb{Z}$?" And so I was like, "Really?" She said, "Yeah!" So I wrote this down: If $n$ is odd, then ...
1
vote
2answers
87 views

Irrationality proof by rational approximations

Assume we have a sequence of rational numbers $\left(\frac{p_n}{q_n}\right),$ where $\gcd(p_n,q_n)=1, \ \forall n \in \mathbb N$. We know that $$\lim_{n\to\infty} \left(\frac{p_n}{q_n}\right)= x$$ ...
2
votes
4answers
204 views

How do I show that $\gcd(a^2, b^2) = 1$ when $\gcd(a,b)=1$? [duplicate]

How do I show that $\gcd(a^2, b^2) = 1$ when $\gcd(a,b)=1$? I can show that $\gcd(a,b)=1$ implies $\gcd(a^2,b)=1$ and $\gcd(a,b^2)=1$. But what do I do here?
2
votes
3answers
305 views

Show that $\gcd(a + b, a^2 + b^2) = 1\mbox{ or } 2$ [duplicate]

How to show that $\gcd(a + b, a^2 + b^2) = 1\mbox{ or } 2$ for coprime $a$ and $b$? I know the fact that $\gcd(a,b)=1$ implies $\gcd(a,b^2)=1$ and $\gcd(a^2,b)=1$, but how do I apply this to that?
2
votes
1answer
95 views

Greatest common divisor of $n!$ and $ H_n n!$

Let $H_n$ be the $n$th harmonic number, ie. $H_n=1+\frac{1}{2}+\frac{1}{3}+ \cdots+\frac{1}{n} .$ I would like to get the value of $\gcd(n!,H_n n!)$, where $\gcd$ is the greatest common divisor, ie, ...
3
votes
1answer
55 views

Proving that $\sqrt{n^2+1}-n = F(n), n \in \mathbb{N}_{>0}$

Let $F(n)$ denote a infinite continued fraction of form such that: $$F(n) = \cfrac{1}{2n + \cfrac{1}{2n + \cfrac{1}{2n + \cfrac{1}{2n + \cfrac{1}{\dots}}}}}$$ Consider the following equation: ...
17
votes
5answers
998 views

Bézout's identity proof that if $(a,b,c)=1$ then $ax+bxy+cz=1$ has integer solutions

Massive edit to simplify the question. Some comments below might be made obsolete - specifically, the comment that this follows directly from Dirichlet. That was true for the original wording. I'm ...
4
votes
2answers
67 views

Finding all integers $n$ such that $\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$ has exponent $2$

This problem is from a past qualifying exam. Definition A group $G$ has exponent $e$ if $g^e=1$ for all $g\in G$. Problem Let $G=\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$. Find all the ...
0
votes
0answers
74 views

Let $m,n,o \in \mathbb{N} $, when $o$ is $m+n$?!

let $ \mathbb{N}:=\{ \emptyset, (\emptyset)^+, ((\emptyset)^+)^+,...,(...((\emptyset)^+)^+...)^+,...\} $, $n \in \mathbb{N} $ with $ I_n:=\{t \in \mathbb{N}|t \leq n\} $ $ I_n^*:=I_n\backslash \{0\} ...
2
votes
0answers
3k views

Prove all base 10 positive integers are divisible by 3 if the sum of their digits is divisible by 3 [duplicate]

I came across a strange property of $3$ in base $10$; for all integers I have tried, the following rule seems to be true: The integer '$n$' is divisible by $3$ if the sum of the digits of the ...
2
votes
1answer
211 views

Number of digits and last digit of a number

How can I find the number of digits and the last digit of the number $$\large{2357^{2357^{.^{.^{.^{2357}}}}}}$$ Basically $2357$ to the power of $2357, 2357$ times.
6
votes
3answers
521 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
247 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
193 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
69 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
269 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
169 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
126 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, ...
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
207 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
455 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
100 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
136 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
153 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
606 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
111 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
40 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
152 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
80 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
106 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
235 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
737 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
134 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
71 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: ...