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

learn more… | top users | synonyms (1)

0
votes
0answers
9 views

How do Quadratic Fields look on Complex Planes

I have spent a long time trying to seek some information of quadratic fields. Can someone show me a complex plane around the origin, with the points on the part of the complex plane which are ...
9
votes
0answers
30 views

Finding triplets $(a,b,c)$ such that $\sqrt{abc}\in\mathbb N$ divides $(a-1)(b-1)(c-1)$

When I was playing with numbers, I found that there are many triplets of three positive integers $(a,b,c)$ such that $\color{red}{2\le} a\le b\le c$ $\sqrt{abc}\in\mathbb N$ $\sqrt{abc}$ divides ...
0
votes
2answers
15 views

If every prime that divides $n$ also divides $m$, show that $\phi(mn)=n\phi(m)$ & $\phi(mn)=m\phi(n)$

If every prime that divides $n$ also divides $m$, show that $\phi(mn)=n\phi(m)$ & $\phi(mn)=m\phi(n)$ My attempt. As every prime that divides $n$ also divides $m$ implies $(m,n)=d$ where ...
2
votes
1answer
29 views

Largest possible subset primes

Let $q$ be a Sophie Germain prime number, i.e. $2q+1=p$ is prime. Consider the set $\{1,2,3,\ldots,p-1\}$. Then what is the maximum size of a subset of this set, such that the subset contains no two ...
1
vote
0answers
17 views

Quadratic Field of $Q[√−1]$…

Can someone show me a complex plane around the origin, with the points on the part of the complex plane which are quadratic integers in $Q[√−1]$. Another graph for $Q[√−3]$. And another for $Q[√−5]$. ...
1
vote
1answer
28 views

Prove that $\phi(n)=\frac{n}{2}$ iff $n=2^k$ for some integer $n$

Prove that $\phi(n)=\frac{n}{2}$ iff $n=2^k$ for some integer $n$ Attempt: Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Then $\phi(n)=\frac{n}{2} \implies ...
0
votes
1answer
15 views

Primes in Quadratic Fields with Norm less than 6

What are the primes in $\mathbb Q[\sqrt{−1}]$ which have norm less than $6$? Also what primes in $\mathbb Q[\sqrt{−3}]$ have norm less than $6$, and the primes in $\mathbb Q[\sqrt{−5}]$? Which of them ...
0
votes
1answer
21 views

Show that $ζ$ is a Quadratic Integer in $Q[\sqrt{−3}]$

So in the complex plane, there are three cube roots of one. Suppose we let $ζ$ be the cube root of one which has positive imaginary part. How can we show that $ζ$ is a quadratic integer in ...
5
votes
2answers
109 views

What is the ten's digit of $7^{7^{7^{7^7}}}$

What is the ten's digit of $\zeta=7^{7^{7^{7^7}}}$. I got this question while doing binomial theorem. I think that $7^4=2401$ and we only need $\zeta\pmod{100}$. All I could think of is already ...
1
vote
1answer
44 views

How Deficient a Number is? (Finding numbers having a certain deficiency)

This question was edited, in particular equations were corrected: A number N is said to be deficient by an integer $d$ if: $\sigma(N)=2N-d$ Note that powers of 2 are deficient by 1. While a prime ...
11
votes
1answer
149 views

A proof involving the Euler phi function

Problem: Let $\varphi$ be the Euler phi function, where for any $n \in \mathbb{Z^+}$, $\varphi(n)$ is the number of positive integers less than $n$ that are relatively prime with $n$. ...
-1
votes
2answers
46 views

Solving $a^2$ $+$ $ b^2$ $=$ $2c^2$ [on hold]

I was working through some number theory problems , when I came across the following question : Find all solutions of $a^2$ $+$ $b^2$ $=$ $2c^2$ Can someone help me out ? Maybe a hint ...
7
votes
4answers
204 views

Understanding the trivial primality test

I'm reading an algorithms book and I came across a code example for a primality test. The problem is that I couldn't understand the condition for the for-loop: ...
1
vote
1answer
34 views

How can I find the common solution for the following linear congruences : [on hold]

How can I find the common solution for the following linear congruences : $1.)$ $x \equiv 5 \pmod {13}$ $x \equiv 3 \pmod {12}$ $x \equiv 2 \pmod{35}$ $2.)$ $x \equiv 2 \pmod{35}$ $x \equiv ...
7
votes
3answers
97 views

Irrational Numbers : Show that $0.1248163264…$ is irrational

I was working through some basic Number Theory Problems in Rosen and came across the following problem : Show that the real number $0.1248163264...$ represented in ...
0
votes
3answers
36 views

Diophantine Equations : Solve $a^2 + b^2 = 4c + 3$

I was working my way through some number theory problems , when I came across the following question : Find all solutions to the equation $a^2 + b^2 = 4c + 3$ My Solution (partial) : If ...
8
votes
2answers
108 views

Divisibility of $6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$

Prove or disprove that for all natural $n$ $$6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$$ is divisible by $259$. I tried to apply mathematical induction, but ...
-1
votes
3answers
43 views

basic word problem! [on hold]

Find the smallest number by which $108$ must be multiplied to give a multiple of $80$.
3
votes
3answers
29 views

Largest subset with no arithmetic progression

I am trying to find some weak bounds on the largest subset of a set, such that the subset has the property that it contains no three elements in arithmetic progression. The elements of the original ...
0
votes
3answers
40 views

Number of times $2^k$ appears in factorial

For what $n$ does: $2^n | 19!18!...1!$? I checked how many times $2^1$ appears: It appears in, $2!, 3!, 4!... 19!$ meaning, $2^{18}$ I checked how many times $2^2 = 4$ appears: It appears in, ...
1
vote
3answers
41 views

How to apply Chinese Remainder Theorem for $x$

If: $$x \equiv 0 \pmod{17}$$ and $$x \equiv -1 \pmod{9}$$ Then how is: $$x \equiv 17 \pmod{153}$$ I get that since $\gcd(9, 17) = 153 $ the solution will be $\pmod{153}$ but how do you get the $17 ...
2
votes
2answers
67 views

Let $m$ be the least positive integer divisible by $17$ whose digits sum to $17$. Find $m$.

Let $m$ be the least positive integer divisible by $17$ whose digits sum to $17$. Find $m$. $m$ is a 3 digit number (because this was an AIME problem). $$m \equiv 0 \pmod{17}$$ $$m \equiv 17 ...
5
votes
5answers
74 views

solutions such that a combination number is odd

Let $m$ be a positive integer. Given $m$, I want to find the largest $n$, $1\leq n\leq m$, such that $$m+n\choose n $$ is odd. Is there any standard theorems or results? Any references? Thanks!
2
votes
3answers
65 views

$a^2 = 2b^3 = 3c^5$ Find the smallest value of $abc$.

We have following equation: $a^2 = 2b^3 = 3c^5$ Where $a, b, c$ are natural numbers. Find the smallest possible value of product $abc$.
1
vote
1answer
23 views

Number of $q$-th residues modulo $n$

Let $q$ be a prime and $n\ge 2$ an integer. Moreover, define $f_q(n)$ as the number of $q$-th residues modulo $n$. Is it true that if $K$ is a positive constant then there exist infinitely many $n$ ...
1
vote
4answers
54 views

Is $\gcd(2^{2n}+1, 3)=1$?

Can any one prove that $2^{2n}+1$ and $3$ are relatively prime for any integer $n$? I tried with a Matlab program and computed this gcd upto $n= 25$. I got 1 for all of them. So I suppose that the ...
3
votes
12answers
2k views

Measure 11 liters using bottles of 16, 6, and 3 liters

This question has been bugging me for a day and finally I gave up and decided to ask the community for it so here's how it goes: Suppose we have 3 bottles with capacities of $16,6$ and $3$ liters, ...
0
votes
2answers
46 views

Construction of Natural Numbers

I am trying to prove that the natural numbers can be constructed from the product of a power of $2$ and an odd number. For all $n \neq 0$ in the natural numbers, $n = (2k+1)(2^p)$, where $k$ and $p$ ...
5
votes
0answers
77 views

A problem about $e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$

Let $\alpha_i\in [0,1),\; i\in \{1,\cdots,N\}$ for some positive integer $N$, such that $$e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$$ and if for any non-empty proper subset ...
0
votes
2answers
59 views

Find all solutions of equation $x^{23}=5$ in $\Bbb Z_{23}$

I just found that $5$ is a solution by using Fermat's theorem. But, I am not sure whether there are more solutions and how I could find them...
23
votes
3answers
2k views

Is it possible for integer square roots to add up to another?

I initially was wondering if it were possible for there to be three $x,y,z \in \mathbb{Q}$ and $\sqrt{x},\sqrt{y},\sqrt{z} \notin \mathbb{Q}$ such that $\sqrt{x} + \sqrt{y} = \sqrt{z}$. I had ...
1
vote
1answer
160 views

Isn't really a monotonic sequence?

First, I'd to say that I'm a beginner so may you answer easily plz. I'll expose you the problem: I was looking up on this page http://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF and find ...
0
votes
0answers
41 views

Prove that if $(n-1)!\equiv-1 \mod n$ then $n$ is prime. [duplicate]

Let n be a natural number, $n\ge 2$. Prove that if $(n-1)!\equiv-1 \mod n$ then $n$ is prime. I tried few things but I my skills in equations modulo $n$ are not well enough. I would really appreciate ...
4
votes
2answers
106 views

How do I prove that $ f(n) = (n + 1)! - 1 $ is an injective function?

I have this problem: Consider the function $f : \mathbb{N} \rightarrow \mathbb{N}$ defined, for every $n \in \mathbb{N}$, by $$f(n) = (n+1)! - 1$$ Prove that $f$ is injective. How do I ...
0
votes
2answers
18 views

Sum of polynomial coefficient

Steve says to Jon, "I am thinking of a polynomial whose roots are all positive integers. The polynomial has the form $P(x)=2x^3-2ax^2+(a^2-81)x-c$ for some positive integers $a$ and $c$. Can you ...
2
votes
2answers
35 views

How many distinct numbers can I get mod 8

so I have the following $(0,1\ \text{or}\ 4)+(0,1\ \text{or}\ 4)+(0,1\ \text{or}\ 4)$ I want to see how many distinct numbers can I get mod $8$ by adding from this list 3 times for example I got so ...
1
vote
3answers
37 views

Given $n \in \Bbb Z$, determine $\gcd(3n^2 + 7n + 4, n + 2)$.

I factored $3n^2+7n+4$ to $(3n+4)(n+1)$ and because there isn't a common factor of those and $n+2$ I said that the gcd is $1$, but is there any othere way to go about it that would come up with a gcd ...
-1
votes
4answers
49 views

Find the last digit of $\binom{2016}{21}$

Find the last digit of the binomial coefficient: $$\binom{2016}{21}$$ I would start by factorial form: $$\binom{2016}{21} = \frac{2016!}{21!(1995!)}$$ But that doesnt help much?
2
votes
1answer
36 views

Prove that $2$ is irreducible in $\mathbb{Z}[\sqrt{n}]$ if $n$ has a prime factor congruent to $5$ modulo $8$.

Prove that $2$ is irreducible in $\mathbb{Z}[\sqrt{n}]$ if $n$ has a prime factor congruent to $5$ modulo $8$. I know that if $x^2 \equiv \pm2 \pmod p$, where $p$ is a prime, has no solution if ...
15
votes
2answers
97 views

For $N\in \mathbb{N}$, do there exist natural numbers $N<n_1<n_2<\cdots<n_k$ such that $\frac{1}{n_1}+\cdots+\frac{1}{n_k}=1$?

$N$ is a natural number. Is there any $k$ and some natural numbers $N<n_1<n_2<\cdots<n_k$ such that $$\frac{1}{n_1}+\frac{1}{n_2}+\cdots+\frac{1}{n_k}=1$$?
6
votes
4answers
80 views

Prove that if $p$ is a prime such that $p^2+2$ is a prime then $p=3$.

My problem in my solution is that I don't know if the operations I apply on congruence modulo n are admissible. I could really use some guiding: Attempt: Let there be $p\ne 3$ fulfilling the ...
4
votes
3answers
63 views

Prove that ${x^2+y^2=z^n}$ has a solution in $\mathbb{N}$ for all $n$ in $\mathbb{N}$

I am solving it by stating that $$x^2 +y^2 =c^2$$ represents a circle. And when $$c^2=z^n$$ then , it represents a system of concentric circles with radius varying as $z$ varies or $n$ varies. So, for ...
1
vote
0answers
27 views

$\sum_{n=i}^{j}\frac{1}{n}$ Isn't Integer Without Bertrand's Postulate [duplicate]

$i,j\in \mathbb{N}$ and $i<j $. Prove that $$\sum_{n=i}^{j}\frac{1}{n}$$ isn't integer using without using the Bertrand's postulate.
2
votes
1answer
16 views

Invariance Principle Question

A circle is divided into six sectors. Then the numbers $1, 0, 1, 0, 0, 0$ are written into the sectors (counter-clockwise say). You may increase two neighboring numbers by $1$. Is it possible to ...
14
votes
3answers
919 views

A fun problem by Arnold using the Poincaré recurrence theorem

I came across this problem by V. I. Arnold while studying his classical mechanics book. Consider a sequence where the $n^{th}$ term is made up by considering the first digit of $2^n$, the first ...
2
votes
1answer
52 views

Using Fermats prime numbers to prove that there is infinitely many prime numbers

A Fermat number $F_n$ is of the form $F_n = 2^{2^n} + 1$ Furthermore, $F_n = 2 + F_0F_1F_2......F_{n-1}$ Now I already proved that if $n \neq m$ then $\gcd(F_n,F_m) = 1$ Here is the proof Without ...
1
vote
2answers
20 views

Proving expressibility of integers as the difference of two squares.

I'm given the task: Prove that a positive integer is expressible as the difference of two squares of integers if and only if it is not of the form $4n+2, n\in\mathbb{Z}$ I was given a hint that I ...
2
votes
0answers
20 views

Argument verification fermat divisors.

any prime divisor of p is of the form then p = k $2^{n + 1}$ + 1 for n $\geq$ 2. We can use the result that Any divisor of $F_n$ is of the form q = k * $2^{n + 1}$ + 1 (*) Given that $F_n$ = ...
0
votes
1answer
19 views

Proof involving primitive Pythagorean triples

Currently learning about primitive Pythagorean triples and I'm having trouble approaching the following proof. Given that $x, y, z$, is a primitive Pythagorean triple with $y$ even, I need to show: ...
4
votes
1answer
41 views

Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \le j \le n$

Let $p$ be a prime number and $a_1, a_2, \ldots, a_n$ be integers. Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \leq j \leq n$. The hint was to use induction. ...