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

learn more… | top users | synonyms (1)

0
votes
1answer
24 views

Need help with the proof of a theorem about Gaussian integers

Theorem 6-3. If $\alpha$ and $\beta$ are integers of $Z[i]$, and $\beta \neq 0$ then there are $\kappa$ and $\rho$ in $Z[i]$ such that $$\alpha =\beta\kappa+\rho, \text{ } N_\rho < N_\beta$$ ...
0
votes
4answers
50 views

How can be proven that any number X is greater,lesser or equal to any other number Y?

I have looked for it on the internet, really, but all I have found are particular cases like 1 > 0, or such. Is there an algebraic proof for proving that x > y or, x = y, or x < y? I thought of ...
2
votes
0answers
44 views

If $L > 1$ is an odd almost perfect number with $\omega(L)=6$, then $L$ must be divisible by $3$.

Edited July 15 2016 Let $\mathbb{N}$ denote the set of positive integers. Let $\sigma = \sigma_{1}$ denote the (classical) sum-of-divisors function. Let $I(x) = \dfrac{\sigma(x)}{x}$ denote the ...
4
votes
2answers
34 views

Smallest chain of consecutive integers not all coprime

Let $t$ be a positive integer. What is the smallest $t$ for which we can find an integer $a$ such that each element of the set $\{a+1,a+2,\dots ,a+t\}$ is not coprime with all other elements of the ...
2
votes
0answers
51 views

lower bound for sum of distinct n-th roots of unity

Given a positive integer $n$, define $\zeta = e^{2\pi i/n}$ and define $s: \mathbb Z^n \to \mathbb C$$$s(\vec x) = \sum_{k=0}^{n-1} x_k \zeta^k$$ Let us consider the set $S = \{ |s(\vec x)| : \vec x \...
1
vote
2answers
39 views

Can it proved that the GCD does not divide the integer coefficients in the linear form of the GCD?

Let $d = (a,b)$ then $d = ax +by$ for some $x,y \in \mathbb{Z}$ I want to prove that $d \nmid x,y$. Motivation I'm trying to solve the following problem: If $a$ is prime to $b$ and $y$, $b$ is ...
2
votes
8answers
196 views

Showing that $2^6$ divides $3^{2264}-3^{104}$

Show that $3^{2264}-3^{104}$ is divisible by $2^6$. My attempt: Let $n=2263$. Since $a^{\phi(n)}\equiv 1 \pmod n$ and $$\phi(n)=(31-1)(73-1)=2264 -104$$ we conclude that $3^{2264}-3^{104}$ is ...
3
votes
1answer
168 views

Generalization of Inkeri's primality test

How to prove that following hypothesis is true ? Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are ...
0
votes
2answers
22 views

Prove that the modular congruence holds: $b^d$ $=$ $r \pmod n$, $b^{d/q}$ $=$ $x \pmod n$, then $x^q$ $=$ $r \pmod n$.

Prove that if $b^d$ $=$ $r \pmod n$ $b^{d/q}$ $=$ $x \pmod n$, then $x^q$ $=$ $r \pmod n$ for any integers $b$, $n$, $r$, and $q$ (which divides $d$). Or more simply that $b^d$ $=$ $x^q$ $\...
0
votes
0answers
34 views

Need help with the proof of the following theorem about orders

Theorem 4-7. If any integer belongs to $t\pmod p$, then exactly $\varphi(t)$ incongruent numbers belong to $t\pmod p$ Proof: Assume that $\operatorname{ord}_p a=t$. Then by theorem 4-4, $t\mid (p-1)$,...
2
votes
0answers
20 views

can we have probabilistic interpretation of $L(1,( \frac{\cdot }{ p}))^{-1}$

the zeta function has a probabilistic interpretation: $$ \zeta(2)^{-1}= \prod_p \left( 1- \frac{1 }{p^2 } \right) $$ can we have probabilistic interpretation of $L(1, \frac{\cdot }{ p})$ which ...
0
votes
4answers
65 views

Question about rational roots of polynomial

Let $p(x) = c_0 + c_1x + \ldots + c_d x^d$ be a polynomial with integer coefficients $c_0, \ldots, c_d \in \mathbb{Z}$ and $c_d \neq 0$, so $p(x)$ has degree $d$. Let $a/b$ be a rational root of $p(x)$...
4
votes
1answer
61 views

All $n \in \mathbb{N}$ such that if $a^2 \leq n$ where $a$ is odd, then $a|n$

Find all $n \in \mathbb{N}$ such that if we have $a^2 \leq n$ where $a$ is an odd integer, then we also have that $a$ divides $n$. I tried various methods on this like using $a|n$, $a-2|n$, $a-4|n$, ...
0
votes
1answer
37 views

Visualizing Greatest Common Divisor (gcd)

If a divides b and leaves a remainder c, then gcd (a,b)= gcd (a,c). The book has given a detailed proof for it. But I want to understand it intuitively. On diving 15 with 4, remainder is 3. And gcd ...
2
votes
2answers
101 views

Find all positive integers satisfying: $x^5+y^6=z^7$

Find all positive integers satisfying: $x^5+y^6=z^7$ No algebraic method came into my mind,just tried to find some answers and failed! Of course it's very simple to write a computer program finding ...
0
votes
2answers
34 views

How do I see that $a = bu$ for some unit $u$? [duplicate]

Suppose elements $a$ and $b$ in a domain satisfy $a \mid b$ and $b \mid a$. How do I see that $a = bu$ for some unit $u$?
2
votes
2answers
105 views

Find an irrational number $n$ such that $n^n$ is a rational number.

Find an irrational $n$ such that $n^n$ is a rational number. I have some tries to find this... I have tried so much numbers but no success. How can I find them.
1
vote
1answer
42 views

how can i rewrite or derive a decimal representation into a diophantine equation?

How can i convert the form \begin{equation} \label{eq:(3)} {\overline{a \ldots ab \ldots b}}_{(10)} = y^2, \end{equation} (Suppose that $ 1 \leq a \leq 9$ and $0\leq b \leq 9$ are two integers, not ...
1
vote
1answer
25 views

Anti-associativity of product of sum of squares

$\newcommand{\P}{\mathbb{P}}$$\newcommand{\Z}{\mathbb{Z}}$ Let $\P$ be the set of prime numbers congruent to $1 \pmod 4$. I know that for every $p \in \P$ there's a unique couple $(a^2,b^2)\in \Z^2$ ...
2
votes
1answer
44 views

When a congruence system can be solved?

How to prove that a congruence system with $n$ equations can be solved if and only if all the equations can be solved two by two? \begin{cases} x \equiv a_1 \phantom ((mod\phantom mm_1) \\ x \equiv ...
0
votes
1answer
44 views

Maximum Coin Changes That Does Not Add To a Dollar

What is the maximal amount of money attained from coins of 1, 5, 10, 25 cent denominations that none of its subset amounts to 100 cents? We can find the solution with exhaustive or naive dynamic ...
1
vote
2answers
38 views

A question concerning the Euclidean algorithm

Given a pair of relatively prime integers $m$ and $n$, with $|m| + |n| > 1$, can I always find integers $a$ and $b$ such that am + bn = $\pm$ 1 and $|m| + |n| > |a| + |b|$.
1
vote
3answers
74 views

Prove that if $ a^2$ divides $a$, then $a$ is in ${-1,0,1}$

Having a little trouble writing a proof of this one: Prove that if $a^2$ divides $a$, then $a \in \{-1,0,1\}$ Thanks!
0
votes
0answers
36 views

Is there a general solutions to min(Floor(N/a), Floor((N ± a)/r))?

I am looking for a general solution to $\min\left({\left\lfloor{\frac{N}{a}}\right\rfloor, \left\lfloor{\frac{N \pm a}{r}}\right\rfloor}\right)$ where $N$, $a$, and $r$ are positive integers with the ...
0
votes
5answers
84 views

If $a+b=c+d$ and $0<a<b<c$ then is it true $ab>cd$?

If $a+b=c+d$ and $0<a<b<c$ then is it true $ab>cd$? This is the only thing I know: $\text{min}(a,b,c,d)=d$ as $d=a+(b-c)<a$. So it might be true that the inequality holds. I've ...
4
votes
1answer
28 views

Question on proof regarding solvability of congruences modulo powers of 2

The following theorem was left as an exercise in K. Ireland and M. Rosen's A Classical Introduction to Modern Number Theory. The theorem is as follows: Let $2^l$ be the highest power of 2 dividing ...
3
votes
1answer
1k views

IMO 2016 Problem 3

Let $P = A_1 A_2 \cdots A_k$ be a convex polygon in the plane. The vertices $A_1, A_2, \ldots, A_k$ have integral coordinates and lie on a circle. Let $S$ be the area of $P$. An odd positive integer $...
7
votes
0answers
74 views
+50

Greedy algorithm Egyptian fractions for irrational numbers - patterns and irrationality proofs

This is related to another question on this site, but it's not a duplicate, because the actual questions I ask are completely different. In one of the answers Jeffrey Shallit provided a very useful ...
4
votes
1answer
93 views

Find all positive integers $k,m,n$ satisfying: $\frac1k+\frac1m+\frac1n=\frac{1}{1996}$

Find all positive integers $k,m,n$ satisfying: $\frac1k+\frac1m+\frac1n=\frac{1}{1996}$ The trivial answer is: $k=m=n=3*1996$ $kmn=1996(km+mn+nk)=499\times4\times(km+mn+nk)$ , now $kmn$ must be ...
3
votes
0answers
88 views

$\sqrt[n]{m}$ is irrational if $m$ is not the nth power of an integer

I'm reading the book A Classical Introduction to Modern Number Theory by Ireland and Rosen, and I think that there is an exercise which is false. The exercise says: Prove that " $\sqrt[n]{m}$ is ...
2
votes
1answer
39 views

$a \in \mathbb{Z}[i]$ is a unit if and only if $a$ divides every element of $\mathbb{Z}[i]$? [closed]

As the question title suggests, how do I see that $a \in \mathbb{Z}[i]$ is a unit if and only if $a$ divides every element of $\mathbb{Z}[i]$?
3
votes
1answer
27 views

Does it necessarily follow that $a = ub$ for some unit $u \in \{\pm1, \pm i\}$? [closed]

Suppose that $a$, $b \in \mathbb{Z}[i]$ satisfy $a \mid b$ and $b \mid a$. Does it necessarily follow that $a = ub$ for some unit $u \in \{\pm1, \pm i\}$?
1
vote
0answers
15 views

If $N \neq p^k$, $(\sigma(N) - N) \mid (N - 1)$, and $3 \mid (N - 1)$, does it follow that $\nu_{3}(\sigma(N) - N) \neq \nu_{3}(N - 1)$?

(Note: This has been cross-posted from MO.) The title says it all. Let $\sigma=\sigma_{1}$ be the classical sum-of-divisors function. Here is my question: Original Problem (Note: This has been ...
0
votes
3answers
43 views

Prove $a \equiv b \pmod{c} \implies a^n \equiv b^n \pmod{c}$.

Prove $a \equiv b \pmod{c} \implies a^n \equiv b^n \pmod{c}$. Here is my proof, which I'm slightly doubtful I've done correctly: Suppose $a \equiv b \pmod{c}$ and $d \equiv e \pmod{c}$ We have: $...
1
vote
3answers
36 views

Is this enough to prove that the GCD is larger?

Prove that $(a+b, a-b) \geq (a, b)$ My attempt Let $(a+b, a-b) = d$ and $(a, b) = c$. Since $c \mid a,b$ $c$ is also a factor of $a+b$ and $a-b$. Thus $c \leq d$. Is this enough as a proof? It ...
2
votes
1answer
36 views

$a_i \mid r $ implies that $r = 0$ if $0 \leq r < a$?

If $x$ is any common multiple of $a_1, a_2 \cdots a_n$ all $\neq 0$ then prove that $[a_1, a_2,\ldots,a_n]$ divides $x$. Note, $[a_1, a_2,\ldots,a_n]$ is LCM. The solution provided in my text: Let $...
1
vote
0answers
33 views

Steep Diagonals and Magic Squares - Prove and State a Theorem

We want to describe via a picture a set of subsets of a square which are something like diagonals, but are not quite the same. We’ll call them steep diagonals. One of them, labelled e, is illustrated ...
-2
votes
1answer
52 views

Is this possible to solve? [closed]

If a, b, c are different prime numbers such that (a-b)(a-c) = 255, find the value of b + c.
0
votes
1answer
49 views

Need help with the proof of the following theorem

Theorem: If $ord_{m}a=t$, then $ord_{m}a^n=t/(n,t)$ Proof: Let $(n,t)=d$. Then since $a^t \equiv 1(mod\text{ } m)$, we have $$(a^t)^{n/d}=(a^n)^{t/d} \equiv 1(mod\text{ } m)$$, so that if $ord_{m}...
1
vote
1answer
36 views

Need help with the following theorem

Theorem 4-5. If p is prime and d divides p-1, then there are exactly d roots of the congruence $$x^d \equiv 1(mod\text{ } p)$$ Proof: Since $d|(p-1)$, we have $$x^{p-1}-1 \equiv (x^d-1)q(x)$$ ...
3
votes
2answers
210 views

Percentage of Composite Odd Numbers Divisible by 3

What is the percentage of odd composite positive numbers divisible by 3? In that same vein, what is the percentage of odd composite positive numbers divisible by 5? And, for the future, what is the ...
-3
votes
2answers
45 views

Show that the congruence $3x^2 \equiv 12 \pmod{12}$ has a solution, or not [closed]

Someone know Quadratic residues ? Below: Show that the congruence $3x^2 \equiv 12 \pmod{12}$ has a solution, or not.
2
votes
2answers
60 views

Question about basis step of strong induction proof

Let $P(n)$ be any collection of $n$ coins that can be obtained using a combination of $3$ cent and $5$ cent coins. Use strong mathematical induction to prove that $P(n)$ is true for all integers $n \...
6
votes
0answers
77 views

Is there a finite list of identites in the language of $(\mathbb{N},0,1,+,\times,\mathrm{gcd},\mathrm{lcm})$ that generates all the others?

Let $\Phi$ denote the set of all identities satisfied by $(\mathbb{N},0,1,+,\times,\mathrm{gcd},\mathrm{lcm}).$ Question. Is $\Phi$ finitely axiomatizable? If so, I'd like to see a list of ...
2
votes
0answers
33 views

factoring polynomials in ring of integers modulo powerful number

I am having trouble finding info on how to factor polynomials in ring of integers modulo powerful number. For example: $x^2 - 1$ in $\textbf Z_{8}$. I know by tinkering around that $(x - 1)(x + 1)$...
5
votes
4answers
135 views

Prove that $10^{340} < \dfrac{5^{496}}{1985}$

Prove that $10^{340} < \dfrac{5^{496}}{1985}$. I said since $2^{13} < 10^{4}$, we see that $5 = \dfrac{10}{2} > 10^{\frac{9}{13}}$ and so $10^{340} < \dfrac{10^{343.38}}{1985} <\dfrac{...
0
votes
1answer
32 views

can $4^{2n }$ be written as the sum of “three squares”?

Lagrange theorem says only numbers $n \neq 4^n ( 8k+7)$ can be written as the sum of three squares. what about this one? $$ 4= 2^2 + 0^2+ 0^2 $$ this looks acceptable to me, and yet it is ...
1
vote
1answer
53 views

Find all nonnegative integers $m$ and $n$ such that $m!+1=n^2$. [duplicate]

This question is inspired by Subgroup of Order $n^2-1$ in Symmetric Group $S_n$ when $n=5, 11, 71$. Find all nonnegative integers $m$ and $n$ such that $m!+1=n^2$. We know that $(m,n)=(4,5)$, $(...
1
vote
2answers
54 views

For a prime $p$ if $p^m = p^n+2\cdot p^k$ then $p=3$.

I read an article on commuting graphs of groups and at some point, author gets the equality $|\langle x,Z\rangle| = |Z|\cup 2\cdot |x^G|$ where $Z$ denotes the center of the $p$-group $G$ and $x^G$ ...
1
vote
0answers
30 views

Further references on number theory paper.

Courtesy of the wonderful Canadian Mathematical Society which allows free access to their back issues, I discovered a paper written in 1959 in the Canadian Mathematical Bulletin. The paper answers the ...