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

learn more… | top users | synonyms

1
vote
1answer
47 views

Any odd > 1 is the average of three primes

I think that any odd integer is the average of three primes. My first question is if this is equivalent to some other conjecture/theorem in number theory (I suspect it is). But more importantly, I ...
0
votes
0answers
28 views

Higher solutions to Pell's equation

Let $nm$ be the product of the natural numbers $n$ and $m$. Let $y(1)$ be the lowest solution for certain $d$ to Pell’s equation $x^2-dy^2=1$, and let $y(n)$ be the $n$’th lowest solution. I note for ...
0
votes
0answers
25 views

Logarithmic derivative of Riemann zeta, is this derivation correct?

Let matrix $T_2$ be defined below as the Dirichlet inverse of the Euler totient function as a function of the Greatest Common Divisor (GCD) of row index $n$ and column index $k$; $$T_2(n,k) = ...
1
vote
0answers
18 views

Finding Maximum Value (Related To Least Common Multiple)

Let $l(x,y)$ be the least common multiple of two natural numbers $x$ and $y$. Assume that $1<a<b<c<d$ and $a$,$b$,$c$,$d$ are natural numbers. Find the maximum value of ...
0
votes
1answer
39 views

Proving a set of coordinates is a group.

Here is a homework problem I have from my Abstract Algebra - Number Theory class. I've reprinted it verbatim. I'm a little uncertain how to approach this problem given that the elements of the set $G$ ...
6
votes
2answers
42 views

Number theory problem - contradiction

In an algebraic proof (for my problem it doesn't matter which proof) I have a special setting: $a,b,c \in \mathbb{Z}, \text{gcd}(a,c)=1,b<c \ \text{and} \ a \in \left\lbrace 1, \ldots , ...
0
votes
1answer
28 views

periodic numbers in every basis

We know that a number that is periodic in base $10$ does not need to be periodic in base $2$ for example. My question is if there are numbers that are periodic in every possible base. The non ...
1
vote
1answer
27 views

How to solve this system?

x ≡ 1 mod 5 x ≡ 4 mod 7 x ≡ 8 mod 5 I know the "rule" of posting a tentative of solving before asking for help, but I just don't have what to post here. I tried ...
1
vote
3answers
33 views

A Corollary from Burton's Elementary number theory

This is a corollary from page 160 of Burton Elementary number theory. Corollary. If $p$ is an odd prime, then $p^2$ has a primitive root; in fact, for a primitive root $r$ of $p$, either $r$ or $r + ...
1
vote
1answer
47 views

Subset of prime numbers

Given a subset of prime numbers say $A$. It is given that for $p,q\in A$ we also must have $(pq+4)\in A$ . Show that $A=\phi$ My work so far: It is obvious that $2,3\notin A$ . because all the ...
1
vote
2answers
51 views

Let $t$ be a transcendental number. Prove that the set $\{(a+bt) \mid a,b \in \mathbb{Q}\}$ is not a number field.

Can I just pick a number in the set and then prove it's not constructible? Thx
2
votes
1answer
25 views

Solving a divisibility problem using group theory

Inspired by this I decided to show this: Let $P_n=\displaystyle\prod_{1\leq i<j\leq n} \big(x_i-x_j\big)$ where $x_1\,\dots\, x_n$ are arbitrary integers. Prove $n!\,\big|\, 2P_n$. I am ...
1
vote
1answer
31 views

Fractional part optimization algorithm

I was trying, out of curiosity, to find an efficient algorithm for the problem below which peaked my interest: Let $r$ be a real number. Find an integer $k > 0$ such that $kr$ is "near" an ...
1
vote
1answer
58 views

Does a solution exist where $p,q$ are odd primes and $p^a - q^b = p^c - q^d$ where $a > c > 1$ and $b > d > 1$

From my thinking so far, there is no solution. Is this an open question or is the answer well known? Here's my reasoning about this issue: If a solution exists, then: $$p^c(p^{a-c} - 1) = ...
0
votes
1answer
31 views

Prove $x^i \mod (x^4 + 1) = x^{i \mod 4}$ in $GF(2)[x]$

These are my notes so far: $\frac{x^{i}}{x^4 + 1}$ yields two polynoms $q(x)$ and $r(x)$, s.t. $q(x)(x^4 + 1) + r(x)$ $(x^4 + 1)|(x^{i} - r(x))$ (from 1) We should prove that $r(x)$ = $x^{i \mod ...
0
votes
1answer
40 views

What is the best way of solving for $x,y\in\mathbb N$ given the conditions $\begin{cases}x\mid y+a\\y\mid x + b\end{cases}$?

What is the best way of solving for $x,y\in\mathbb N$ given the conditions $\begin{cases}x\mid y+a\\y\mid x + b\end{cases}$? The letters $a,b\in\mathbb N$ denote constant known numbers. The ...
0
votes
2answers
29 views

Prove that if $d|a$, then $d||a|$

I have no idea where to take this. It says to consider both cases of $d|a$ and $d|-a$, but I don't how to prove that.
1
vote
1answer
40 views

Show there exists a sequence of days within $49$ days where exactly $20$ hrs. are worked

Assume an integer number of hours will be worked each day for $49$ consecutive days. Further assume that at least $ 1 \frac{\text{hrs}}{\text{day}}$ and at most $11 \frac{\text{hrs}}{\text{wk}}$ can ...
0
votes
1answer
24 views

$lcm(a_{1},…,a_{n})=lcm(lcm(a_{1},…,a_{n-1}),a_{n})$

I tried to prove this by complete induction on $n$ but I am having problems in the inductive step: Suppose $$lcm(a_{1},...,a_{n})=lcm(lcm(a_{1},...,a_{n-1}),a_{n}) \forall k\le n\in \mathbb ...
1
vote
5answers
32 views

if $gcd(a,b)=gcd(a,b,c)$ then I need to prove that $ax+by=c$ has solution in $\mathbb Z$

if $gcd(a,b)=gcd(a,b,c)$ then I need to prove that $ax+by=c$ has solution in $\mathbb Z$ that is: $gcd(a,b)|c$ but how can I prove it with the given hypothesis?
1
vote
2answers
95 views

Prove that every number can be written in following form.

Let $$\alpha>0 $$ Prove that every number x can be written in following from $$x=k\alpha +x_1$$ where k is an integer, and $0 \le x_1 < \alpha$. I have tried using archimedianty by using the ...
1
vote
1answer
102 views

Quick question on abundant numbers

is this correct? 1) Show that if $\sigma (n) > 2n$ it follows $ \sigma (kn) > 2(kn)$. Proof: $\sigma (kn) \ge \sum_{d|n} kd = k\cdot \sigma(n) > k2n = 2kn$. How can I show $\sigma (kn) ...
6
votes
2answers
160 views

Writing square root of square-free numbers as sum of square roots.

Some days ago i came across a question about writing $\sqrt {2001}$ as sum of two other square roots. I managed to prove that this is not possible unless one of them is zero and the other one is ...
0
votes
0answers
24 views

prove that $ax+by=b+c$ has solution in $\mathbb Z$ if and only if $ax+by=c$ has solution in $\mathbb Z$

Let $a,b,c,d\in \mathbb Z$ prove that: a)$ax+by=b+c$ has solution in $\mathbb Z$ if and only if $ax+by=c$ has solution in $\mathbb Z$ b)$ax+by=c$ has solution in $\mathbb Z$ if and only if ...
0
votes
2answers
34 views

How can I prove this relation between primes and congruences?

Suppose that $p$ is a prime, and $a\equiv b(\bmod~p)$. Prove that $$a^p\equiv b^p(\bmod~p^2)$$ So, from the first statement, we know that $p|(a-b)$ and that $[a]_p = [b]_p$. Bringing this over to ...
0
votes
1answer
29 views

proof of $lcm(a_{1},…,a_{n})=lcm(lcm(a_{1},…,a_{n-1}),a_{n})$

prove that $lcm(a_{1},...,a_{n})=lcm(lcm(a_{1},...,a_{n-1}),a_{n})$ ($n\in \mathbb N$) By complete induction on n: (n=1,2 are trivial) for n=3: let $c=lcm(lcm(a_{1},a_{2}),a_{3})$ and ...
-1
votes
0answers
25 views

Lowest multiple of N with only 1 and 2 digits

Given a integer N how can quickly find the lowest N multiple such that only contains 1 and 2 in its decimal representation, for example Given 8 the answer would be 112. So far I've tried to use ...
0
votes
2answers
28 views

Primary decomposition of a particular sum

Is there an easy way to see that the sum $$ \sum_{k=0}^{728} (1+2k) $$ has primary decomposition $3^{12}$ ?
1
vote
1answer
30 views

Euler totient function sum of divisors. Theorem 2.2 Apostol

Prove that : $If $ $ n\ge{1} $ $ \sum_{d|n}\phi(d)=N $ $ N \in{\mathbb Z} $ Let S denote the set {1,2,...,n}. We distribute the integers of S into disjoint sets as follows. For each divisor d ...
3
votes
1answer
89 views

Proof of $(ma+ nb, mn)=(a,n)(b,m)$

Let $a,b,m,n \in \mathbb Z$. If $(m,n)=1$ ( $m,n$ are coprime integers) prove that $(ma+ nb, mn)=(a,n)(b,m)$ I started the proof like this: Let $c,d,e$ be the greatest common divisors of ...
0
votes
0answers
31 views

Find $a,b,c \ge 2$ and $p,q$ odd primes where $p^a - 1 = c*q^b$

I've been recently thinking about finding primes $p,q$ where the power of one divides the power of the other when subtracted by $1$. For example, if we remove the requirement that $p,q$ be odd ...
0
votes
1answer
32 views

Finding primes $p$ such that $x\equiv y $ mod $p$

Given values of $x$ and $y$ can we find prime $p$ such that $x\equiv y \mod p$ holds? In other words, how to find the least value of $p$ which divides $\mid x-y\mid$. Is it possible to find value of ...
0
votes
2answers
43 views

Is this solvable: $x^{2}\equiv5\pmod{229}$?

$$x^{2}\equiv5\pmod{229}.$$ Using Legendre symbol, $(\frac{5}{229})(\frac{229}{5})=(-1)^{\frac{4}{2}*\frac{228}{2}}=(-1)^{2*114}=(-1)^{228}=1.$ Hence, 5 is a quadratic residue $mod(229)$ if 229 is a ...
0
votes
1answer
21 views

gcd , lcm problem with divisibility application

How should i prove that $ab|(a,b)[a,b]$ ? Here $(a,b)=gcd(a,b)$ and $[a,b]=lcm(a,b)$. I tried and got an answer as $\frac{ab}{(a,b)}|[a,b]$. then i can also proceed as $[a,b]=(a,b)^2\frac{k}{ab}$. ...
0
votes
0answers
23 views

Miller-Rabin primality test and testing one

I'm learning about Miller-Rabin primality test but in all the problems I see in the notes of a person I got them from, I see that even if he expressed the number as $2^1 \cdot something$, he still ...
5
votes
0answers
67 views

What is known about the solutions to $\varphi(a)+\varphi(b)=\varphi(a+b)$?

As of late I have been researching Euler's Totient function. For the last week or so I have specifically been studying the equation: $\varphi(a)+\varphi(b)=\varphi(a+b)$ While the equation ...
0
votes
0answers
23 views

Taking the modulus of the power?

So I'm learning about Euler's theorem for reducing large powers modulo $n$ and what I'm wondering about is: can we simply take the modulus of a power of a number the same way we take it of the number ...
1
vote
1answer
47 views

How to show $(1^2)(3^2)(5^2)…((p-2)^2)=(-1)^{(p+1)/2}$

I want to show the above problem using Wilson's theorem, which I know is $(p-1)!\equiv(-1)$ mod p. If I start with this I get $1\dot{}2\dot{}3\dot{}...\dot{}(p-1)\equiv(-1)$ mod p, but I don't know ...
5
votes
0answers
35 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
1
vote
1answer
24 views

Question about multiplication of modulars

Why is the property when you multiply two modulars (you multiply the two ones on outside and the two ones inside) Why does that property hold true? Addition is easy but multiplication doesn't make ...
0
votes
1answer
28 views

Congruence and modular arithmetic

$228,547,866$ divided by $q$ leaves the remainder of $r$. Find $r+q$. The problem is designated to be solved by using modular arithmetic. Even though I haven't learned what that is.
5
votes
3answers
196 views

Sums of squares question

If you have $a,b\in\mathbb{N}$ such that $a^2+b^2=M$, are there other natural numbers $c,d$ such that $c^2+d^2=M$? If so, is there an algorithm for generating such pairs or an equation relating them ...
1
vote
0answers
65 views

How to prove $\pi ^{3}$ is not constructible from the fact that $\pi $ is not constructible?

I know how to do this for $\sqrt[3]{\pi }$: First suppose it is constructible and then you just set it equal to $x_{0}=\sqrt[3]{\pi }$ and take the third power of both sides. Then you get ...
6
votes
1answer
107 views

Find all natural numbers such that $\sum_{k=1}^{n} \frac{n^k}{k!}$ is an integer

Find all natural numbers such that $\sum_{k=1}^{n} \frac{n^k}{k!}$ is an integer. I've tried to bring all fractions under commmon denominator and it didn't helped me much. With guessing I find out ...
0
votes
1answer
28 views

Let R = Z/4Z = {0, 1, 2, 3}. Find elements of R[x] which are neither units nor zero divisors.

I know that units are elements that are congruent to 1 modulo 4 when multiplied to some element in Z/4Z. I know that zero divisors are elements that are congruent to 0 modulo 4 when multiplied to some ...
1
vote
3answers
88 views

Proof that any square is of the form $3k$ or $3k+1$

Prove that the square of every natural number is of the form $3k$ or $3k+1$, where $k \in \mathbb{Z}$. I'm trying to reach a contradiction by assuming $n^2 = 3k+2$. Any ideas?
2
votes
1answer
39 views

consecutive prime power

I'm interesting on consecutive prime power numbers. I see that there is the Mersenne primes and the Fermat Primes that give solutions and $(8,9)$. In Sloane collection it is referred on A006549 and it ...
0
votes
0answers
33 views

Method for estimating euler phi without knowing the actual factors.

Is there any method to calculate Euler's totient function $\varphi$ without actually factorizing the number. Estimation of $\varphi$ or determining the range in which its value will lie for a given ...
1
vote
1answer
39 views

If p $\equiv$ 3 (mod 4) with p prime, prove -1 is a non-quadratic residue modulo p.

If p $\equiv$ 3 (mod 4) with p prime, prove -1 is a non-quadratic residue modulo p. I suppose this would not be true if p $\equiv$ 1 (modulo 4). To prove something is a non-square I find to be ...
0
votes
2answers
67 views

Solve and explain diophantine equation

A Diophantine equation ax+by = c always has a solution whenever a and b are relatively prime. Find x ,y such that $$93x-81y=3 $$