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

learn more… | top users | synonyms

1
vote
2answers
137 views

If $a, b, c$ are integers with $a^2 + b^2 = c^2$, then $a$ and $b$ cannot both be odd [closed]

If $a, b, c$ are integers with $a^2 + b^2 = c^2$, it's true that $a$ and $b$ cannot both be odd. But how can we prove it
1
vote
2answers
54 views

field number theory question

If we have ${a+b\sqrt{-1}}$ for a,b in ${Z_p}$, with $p$ as an odd prime, with $\sqrt{-1}^2=-1$, how do we show that $a+b\sqrt{-1}$ has a multiplicative inverse iff $a-b\sqrt{-1}$ has a multiplicative ...
1
vote
2answers
70 views

Is this an acceptable congruency proof?

I have a past exam question that I proved as follows: $$(\forall n\in \Bbb Z)\bigl((3n^2-5\equiv 2 \pmod 4)\lor(3n^2-5\equiv 3 \pmod 4)\bigr)$$ If odd: $$3n^2 - 7 = k4,k\in \mathbb Z$$ $$3(2l+1)^2 - 7 ...
1
vote
1answer
297 views

Show that if $a$ is an even integer and $b$ is an odd integer then $(a, b) = (a/2, b)$

Show that if $a$ is an even integer and $b$ is an odd integer then $(a, b) = (a/2, b)$ Hi everyone, I would like to know if my assumption is justified for answering the above question. Any ...
1
vote
1answer
53 views

Fix $a \in \mathbb{Z} \setminus \{0\}$. Find all integers $n$ such that $\frac{n^3+a}{n^2+a}\in \mathbb{Z}? $

May I know what is the correct approach to tackle the a/m problem? Since $n^3+a$ and $n^2+a$ have no common divisors, in order for $\dfrac{n^3+a}{n^2+a}\in \mathbb{Z},$ we must have $ n^3 +a = n^2 + a ...
1
vote
1answer
97 views

Prove that this sum could'nt be an integrer

let $(p,q)\in\mathbb{N}^{2}$ such that $p\wedge q=1$ ; Prove that $\sum_{j=0}^{j=n}\frac{1}{p+jq}\notin \mathbb{N}$
1
vote
1answer
89 views

How to write the proof for this?

Let $a,b,c \in \mathbb{Z}$, and $a \neq 0$. Use a proof by contradiction to show that if $(a \nmid (bc))$ then $(a \nmid b)$. The symbol $\nmid$ stands for "does not divide". I got the layout, but I ...
1
vote
1answer
138 views

Quadratic Reciprocity - Legendre Symbols

Find the value of $((1\cdot 2)/73)+((2\cdot 3)/73)+...+((71\cdot 72)/73)$. This is based off each fraction being a Legendre Symbol. I tried to find a pattern... but I could't find anything. Also, I ...
1
vote
2answers
159 views

Find the units digit in the number $7^{9999}$.

I have step by step instructions from a previous example to follow, so I figure I know how to get the answer, but I don't understand fully why it works the way it does... By Euler's theorem, if ...
1
vote
1answer
189 views

Prove that $\tau(n) \leq 2\sqrt{n}$ [duplicate]

I'm looking at the following problem: Prove that for a positive integer $n$, $$\tau(n) \leq 2 \sqrt{n}$$ where $\tau(n)$ is the number of divisors of $n$. So my idea was to split the set of the ...
1
vote
3answers
47 views

If $(m,n)=1$ and $mn=r^2$ for $m,n\in\mathbb{Z}^+$, prove that $m$ and $n$ are squares.

Honestly unsure how to proceed with this; I have some thoughts but don't know where to go with them. $(m,n)=1\Longrightarrow m\nmid n$ and $n\nmid m$. But $mn=r^2$, so $\frac{r^2}{mn}=1$, and $mn\mid ...
1
vote
3answers
85 views

Remainder when dividing $3^{10}+3^{10^2}+3^{10^3}+…+3^{10^{100}}$ by $7$

Determine the remainder of dividing $10^{10}+10^{10^2}+10^{10^3}+...+10^{10^{100}}$ by $7$ We have $10\equiv3\pmod7$ then ...
1
vote
1answer
136 views

Is $0$ (zero) a number or an idea? [closed]

I'm fascinated by $0$ (zero) and how all mathematics is integrally tied to its position in our numbering system. But since there is really no way to represent zero outside of it symbol, sort of like ...
1
vote
1answer
43 views

Let $S$ be a set and $p$ a prime number and $m\in N$ such that $p$ does not divide $m$. Show $p$ does not divide $|S|$.

I'm currently doing an exercise where this should be shown: Let $S$ be a set and $p$ a prime number and $m\in N$ such that $p$ does not divide $m$. Suppose $|S| = ...
1
vote
4answers
174 views

How can I find the formula used to produce this number?

In a game, each character has different attributes with values to them. The attributes are things like Strength and Speed and are graded on a scale of 1-100. The game uses a formula to produce an ...
1
vote
1answer
75 views

Legendre Symbols Number Theory

Calculate $\left(\frac{1}{73}\right)+\left(\frac{2}{73}\right)+\cdots+\left(\frac{72}{73}\right)$. I tried to find a pattern and got $1,1,1,1,-1,1,-1,1,1,-1,\ldots$ so I didn't see much of one. I am ...
1
vote
1answer
47 views

Decrypting a message?

I would like to ask for a little help about the following problem, i got stuck in it and have no idea how to proceed to get the answer which Wolfram Alpha gives (of course, i am not allowed to use the ...
1
vote
2answers
397 views

Prove, for any positive integer $n$, that $n -3$ must be a multiple of $5$ if $n^3 -n -4$ is a multiple of $5$.

I had previously solved the problem of proving that $n^3-n-4$ must be a multiple of $5$, given that $n-3$ is a multiple of $5$. I did so by algebraically manipulating $n^3-n-4$ into: $$ ...
1
vote
1answer
80 views

Calculating elements of a particular order

$\newcommand{\ord}{\operatorname{ord}}$ To find all the elements in $(\mathbb Z_{10009}^*,\cdot)$ of order $72$ (without an exhaustive search), I have proceeded in the following manner : For a ...
1
vote
1answer
60 views

Diophantus mathematics

Find a number whose subtraction from two given numbers (say, $9$ and $21$) allows both differences to be squares. Call the required number $9 - x^2$ so that the condition holds automatically.
1
vote
1answer
115 views

GCD = 1 and harmonic numbers, what is the exact asymptotic?

I am looking for the exact asymptotic for this partial sum: $$a(N) = \sum_{n=1}^{n=N}\sum_{k=1}_{GCD(n,k)=1}^{k=n*m} \frac{1}{k}$$ where $m$ is some integer $1,2,3,4,5,...$ My guess was that since ...
1
vote
3answers
98 views

Solve a congruence linear equation.

Solve the following congruence: $19x\equiv 1\;(\text{mod}\;36)$ My work: I found an inverse of $19$ and $36$ which is $9$. $9\cdot 19x\equiv 9\cdot 1\;(\text{mod}\;36)$ $171x\equiv ...
1
vote
2answers
116 views

Two problems on gcd

I'm almost done with the following two problems, but I need to connect the last few dots. 1: Let $a \in \mathbb{Z}$ with $a > 0$. Find $(a,a+2)$ and $(3a+5,7a+12)$. We know that ...
1
vote
2answers
66 views

Is it true that for any natural number $p$, if $p$ divides $ab$, then it divides either $a$ or $b$?

I need someone to check my answer. True or False ? For any natural numbers $p$, if $p$ divides the product $a.b$ of two natural numbers $a$,$b$ in $\mathbb{N}$, then either $p$ divides $a$ or $b$. ...
1
vote
1answer
67 views

Number of ideals in $\Bbb Z[x]/(x^3+1, 7)$

I am trying to find the number of ideals in $R:=\Bbb Z[x]/(x^3+1, 7)$ and $S:=\Bbb Z[x]/(x^3+1, 3)$. I started with $R$ and tried to write it in terms of familiar rings, by using fundamental ...
1
vote
1answer
172 views

help proving this cannot be a perfect square?

Im just not really sure how to go about this. I'm assuming it involves cases where you take m and n to be x mod some number. given integers $m$ and $n$. show that $3^m+3^n+1$ cannot be a perfect ...
1
vote
2answers
47 views

problem proving this property of congruence and primes

I've been working on this for a few days and I just can't seem to find a good proof for this. Given $a \equiv b\pmod{p_i}$, $i=1,2,3,\dots,n$ and $p_i$ is prime, show that $a \equiv b ...
1
vote
1answer
71 views

Can we restrict the average multiplicative order of a number?

We are given a size of a number system, $s$, which is the number of components in the system. For example, the quaternions have $s=4$ components. Now, in general, we will be interested in ...
1
vote
1answer
386 views

Relatively prime numbers

Find the number of elements in the set $\{m:1\le m\le 1000,m$ and $1000$ are relatively prime$\}$. My attempt: We are to find the number of elements which have only $1$ as the common factor with ...
1
vote
1answer
100 views

Measuring the biggest difference in the reduced residue system modulo N

Is there a known means of measuring the biggest difference of consecutive elments of the reduced residue system modulo N? For example, say we have the reduced residue system modulo 15: [1, 2, 4, 7, ...
1
vote
1answer
62 views

On the rational Beatty sequence

Let $S(p/q, b) = \{[pn/q + b]|n\in\mathbb{Z}\}$, where $p, q$ are coprime positive integers and $b$ is any integer, be a rational Beatty sequence. I can't see why the following conclusion is true: ...
1
vote
2answers
244 views

Solve the following system of simultaneous congruences:

\begin{gather} 3x\equiv1 \pmod 7 \tag 1\\ 2x\equiv10 \pmod {16} \tag 2\\ 5x\equiv1 \pmod {18} \tag 3 \end{gather} Hi everyone, just a little bit stuck on this one. I think I am close, but I must be ...
1
vote
1answer
347 views

Ruler Function definition and graphical representation

I was just wondering if anyone would be able to explain what the Ruler Function is and how the sequences of numbers it generates. More specifically, I want to know how the function draws the markings ...
1
vote
2answers
57 views

application on L.C.M and G,C,F

Please I need help on the following problem: The L.C.M and G.C.F of numbers x,18 and 60 are 360 and 6 respectively. What will be the value of x? I know how to find in the case when given two numbers , ...
1
vote
1answer
100 views

Critique on a proof by induction that $\sum_{i=1}^n i^2= n(n+1)(2n+1)/6$?

I need to make the proof for this 1:$$1^2 + 2^2 + 3^2 + ... + n^2=\frac{(n(n+1)(2n+1))}{6}$$ By mathematical induction I know that, If P(n) is true for $n>3^2$ then P(k) is also true for k=N and ...
1
vote
1answer
126 views

Integral form for the euler-mascheroni gamma constant using floor function

Im trying to prove that: $$\gamma = \lim_{n \to\infty} ( \sum_{1}^n \frac{1}{n} - \log(n)) = 1 - \int_{1}^{\infty} \frac{t- \lfloor t \rfloor}{t^2} dt = 1 - \int_{1}^{\infty} \frac{ \{ t \}}{t^2}dt$$ ...
1
vote
2answers
98 views

Problem of Ages (Problema das Idades)

English: Somebody help me with this challenge? It's very confusing: Today, both me and my younger brother are between $10$ and $20$ years old. Also, our ages are expressed by prime numbers and the ...
1
vote
3answers
69 views

$\gcd(a,b_1 \cdots b_k)=1$ if an only if $\gcd(a,b_i) = 1$ for $i = 1,\dots,k$

Suppose that $a,b_1,\dots,b_k$ are integers and I want to show that $\gcd(a,b_1 \cdots b_k)=1$ if and only if $\gcd(a,b_i) = 1$ for $i = 1,\dots,k$. In the direction of assuming $\gcd(a,b_1 \cdots ...
1
vote
2answers
180 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 ...
1
vote
1answer
77 views

Proof that $a\mid b \land b\mid c \Rightarrow a\mid c $

I am trying to prove: $a\mid b \land b\mid c \Rightarrow a\mid c $ $a\mid b$ means that a divides b if there is an integer k, that $b=k\cdot a$ Please give me a hint on how to start, because I ...
1
vote
4answers
74 views

Prove $m=[a,b]\Longleftrightarrow \left(\frac{m}{a},\frac{m}{b}\right)=1$

Was solving some exercise of Number theory, and used this theorem $$m=[a,b]\Longleftrightarrow \left(\frac{m}{a},\frac{m}{b}\right)=1$$Remembered that the teacher showed it in class, but I do not ...
1
vote
1answer
29 views

Correct Demonstration? [duplicate]

If $$\frac{a}{(a,b)}\mid c \;\ \Rightarrow \;\ a\mid b\cdot c$$ $$\frac{a}{(a,b)}\mid c\Rightarrow c=\frac{a}{(a,b)}\cdot k\Rightarrow b\cdot c=\frac{a \cdot b}{(a,b)}\cdot k\Rightarrow b\cdot ...
1
vote
3answers
275 views

multiplicative Euler's $\phi$ function

Here is the pdf and array I am not understanding the proof that $\phi$ is multiplicative function i.e for relatively prime $m,n$ we have $\phi(mn)=\phi(m)\phi(n)$ There were Three Lemmas before the ...
1
vote
2answers
109 views

Mill's Constant Unpublished Extras

The brown paper used in the making of Numberphile's video on Mill's Constant was recently sold on eBay. Here is an image of it, from the eBay listing, The bottom two lines appear on the brown ...
1
vote
1answer
45 views

we need to show gcd is $1$

I need to show if $(a,b)=1,n$ is an odd positive integer then $\displaystyle \left(a+b,{a^n+b^n\over a+b}\right)\mid n.$ let $\displaystyle \left(a+b,{a^n+b^n\over a+b}\right)=d$ $\displaystyle ...
1
vote
1answer
152 views

Prove $\sqrt{k}$ is not a rational number. [duplicate]

Suppose $k>1$ is an integer, and k is not a square number, then $\sqrt{k}$ is not a rational number. Proof: Let $\sqrt{k}=\frac{p}{q}$, and $(p,q)=1$,So $q^2|p^2$, $p\neq 1$, $k$ is not an ...
1
vote
2answers
117 views

Equation $(a-3)cb=a(c+b)$ for natural numbers.

Let $a$, $b$, and $c$ be positive integers. Suppose that $c \leq b \leq a$ and that they satisfy the relation $$ (a-3)cb=a(c+b). $$ What can be said about the solutions?
1
vote
3answers
107 views

Find $n$ such that $x^n \equiv 2 \pmod{13}$ has a solution

I am stuck on the following problem: Consider the congruence $x^n\equiv 2\pmod{13}$. This congruence has a solution for $x$ if $n=5$ $n=6$ $n=7$ $n=8$ Can someone explain in ...
1
vote
1answer
119 views

prove that there are infinite positive numbers $\overline{a_{1}a_{2}a_{3}\cdots a_{n}a_{1}a_{2}a_{3}\cdots a_{n}}$ is square number

Show that there are infinitely many positive integer number $A=\overline{a_{1}a_{2}a_{3}\cdots a_{n}}$,and $0\le a_{i}\le 9$,such that $\overline{a_{1}a_{2}a_{3}\cdots a_{n}a_{1}a_{2}a_{3}\cdots ...
1
vote
1answer
66 views

How $\log p$ distributed?

From literature we know: If a number $n \le x$ is chosen at random, and choose $\lambda \ge 0$ and $j$ not too large (say $\lambda ,j \le 20$) then the number of primes in $[ n , n + \log(n) ]$ is ...