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

learn more… | top users | synonyms

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
84 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
29 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
64 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
106 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
87 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
32 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 $$
0
votes
3answers
45 views

Method of solving extended Euclidean algorithm for three numbers?

I already got idea of solving gcd with three numbers. But I am wondering how to solve the extended Euclidean algorithm with three, such as: 47x + 64y + 70z = 1 ...
2
votes
2answers
57 views

Why is the Legendre symbol not defined for $p = 2$ (even prime)?

Why is the Legendre symbol not defined for $p = 2$ (even prime) ? According to the definition of the Legendre symbol $$\left(\frac a p\right)$$ it is defined for an odd prime $p$ only. Even thus ...
-6
votes
2answers
51 views

Sum of all even numbers that divide $6^6$ [closed]

What is the sum of all even numbers that divide $6^6$. Please tell.
1
vote
0answers
60 views

Proposition 17, p. 68 of Lang's Algebraic Number Theory

I'm stuck on a detail of the following propositon: Let $K, E$ be linearly disjoint number fields with degrees $n$ and $m$ over $\mathbb{Q}$ whose discriminants (over $\mathbb{Q}$) are relatively ...
13
votes
3answers
1k views

Infinity Hotel problem

Q. Welcome to the infinity hotel has an infinite number of rooms 1,2,3,4,... The manager notices all of the rooms have the lights on. He flips the switch every other one. (Rooms 2, 4, 6, …) Then he ...
0
votes
2answers
30 views

Induction question help.

Let $x$ and $y$ belong to a commutative ring $R$ with prime characteristic $p$. Show that, for all positive integers $n$ $$ (( x + y )^p)^n = (x^p)^n + (y^p)^n $$ I hope you can can understand ...
3
votes
2answers
41 views

Proof for the existence of primes not equal to $ap_\alpha +bp_\beta$ etc?

Is there a general proof to show that there exists prime numbers larger than $min(p_\alpha,p_\beta)$that are not equal to $ap_\alpha +bp_\beta$, given $p_\alpha,p_\beta\in\mathbb{P}-\left\{2\right\}$ ...
2
votes
0answers
52 views

Prove that the number of solutions of $a.x^m + b.y^n = c \mod p$ same as $ax^{m'} + by^{n'} =c \mod p$.

This is a question found in Ireland and Rosen's "A classical Introduction to Modern Number Theory", Ch4 Q22. The question was as follows. Q. Prove that the number of solutions (x,y) to the ...
-2
votes
2answers
42 views

divisibility by 3 question

How to show that $3|a(2a^2 + 7)$ where $a$ is an integer? I know this can be proved by mathematical induction.But im searching for an argument like thing to show this
4
votes
1answer
48 views

Confusing verse in “Axiomatic Set Theory” by Patrick Suppes

While searching for prime ordinals, I found this: Goldbach’s Hypothesis is that every even natural number > 2 is the sum of two prime numbers. On the basis of the obvious definition of prime ...
6
votes
2answers
75 views

Showing $2^{n_2} + 3^{n_3}+\cdots+9^{n_9}$ is dense in $\mathbb{R}^+$

I encountered this problem via a friend. He asked me to prove that $$ \left\{u: u= \sum_{k=2}^9 k^{n_k} \quad n_k \in \mathbb{Z} \right\}$$ is dense in $\mathbb{R}^+$. I was able to show that $0$ ...
1
vote
1answer
46 views

Number divides Least Common Multiple(LCM)

Given n and m find the smallest k such that: n divides LCM(m,k) ; m divides LCM(n,k) My Solution : If: (m==n) then k=1 Else: ...
1
vote
2answers
54 views

Find all $n$ such that if $\gcd(a,n)=1$ then $a^2=1$ mod $n$

I really have no idea where to start with this question: Find all $n$ such that if $gcd(a,n)=1$ then $a^2=1$ mod $n$ I found out that it works for $n = 8$, since all odd numbers modulo 8 have order ...
1
vote
1answer
29 views

Smallest sample to produce n%

Q: A Statistic is published that 31% of people think it is okay to smoke in public. What is the smallest sample that could have been interviewed to get this result. A: 13, with 4 "yes" and 9 "no" ...