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

learn more… | top users | synonyms (1)

0
votes
0answers
34 views

Does Inverse of Phi(N) Mod (N) always exist?

Let N=pq where p and q are odd primes and let $\Phi(N)$ be Euler Phi function i.e. $\Phi(7) = 6$ since 6 numbers co-prime to 7 Does the inverse of $\Phi(N) Mod(N^2)$ always exist? It exists if and ...
0
votes
1answer
55 views

Explanation to Fermat's little theorem proof

Fermat's little theorem $\forall a \in \mathbb{Z}$ and every prime p. Then, $a^{p}\equiv a\pmod p$ $a=pm+r $ $\forall 0 \leq r<p$ Proof for $r\not\equiv 0:$ Then, $\forall r \in ...
2
votes
2answers
94 views

Is it divisible by $3^n$?

I need to prove that a number made up exactly $3^n$ $1$s and nothing else is a multiple of $3^n$. Well I think it is true that any number is a multiple of $3^n$ if the sum of its digits is. But I ...
-4
votes
2answers
147 views

Why is minimum solution example to $x^n + y^n = z^n$ comes in the form of three successive integers? [closed]

Can we prove or disprove this conjecture by elementary mathematics: If this is a true statement: $$x^n + y^n = z^n $$where $x, y, z, n$ are positive integers, then there must be a minimum integer ...
3
votes
0answers
64 views

When does $a^b\mid b^a$

Let $a,b >1$ be integers. When does $a^b \mid b^a$? Certainly if this is true then $a\mid b$ by considering $a$'s prime factors. (not quite convinced). Also then if $b$ is prime then $a=b$. ...
0
votes
1answer
75 views

Congruence - Number Theory

Prove that $2005^{2005}$ is not the sum of two perfect cubes. I have looked at some mods but none have given me anything useful as of yet. I looked at the usual mods such as $4, 5, 7, 11, 13$ but ...
0
votes
0answers
17 views

Proving the Well Ordering Property of $\mathbb{Z}$ by induction and prove the minimal element is unique.

I would like a verification of this proof. (Am I using induction?) Claim: $\mathbb{Z}$ is well ordered and there exists a unique minimal element. Assumptions: There are no repeated members in ...
0
votes
0answers
19 views

Number theory questio [duplicate]

I have studied for about 250 questions and there are many questions i can't take.. i considered but i don't know how to start... how can i solve this? In second question, there even hint.. Well ...
1
vote
1answer
44 views

Solving the equation $x^3+y^2=4x^2y$ over integers.

$$x^3+y^2=4x^2y$$ This is a quadratic in $y$, the discriminant of which must be $>0$ $$\implies 16x^4-4x^3>0$$ $$\implies x \text { belongs to } (-\infty,0) \cup (1,\infty)$$ (So we have ...
1
vote
0answers
61 views

The sum of the greatest common divisors

What are the values for the positive numbers $a,b$ and $c$ can take the expression $$(a^2,b^2)+(a,bc)+(b,ca)+(c,ab)?$$ (Here $(u,v)=\gcd(u,v)$ - the greatest common divisor for $u\in \mathbb N, ...
0
votes
1answer
26 views

Fibonacci sequence property

I think its proof will be simple but. I dont know well When the difference of number of sequence in fibonnaci is 1 or 2, i know how to prove but this is not
0
votes
0answers
9 views

Explain following Congruences in elementry way

While studding David M Burton I am felling difficulties with Linear Congruence is there any another way expertise this area (online resources). And how can I show that $21x \equiv 49\ (mod\ 10)$ can ...
3
votes
0answers
43 views

Sum of integer squares with zero sum

This is something that I perhaps should know but don't. What is known about sums $\sum_{i=1}^k a_i^2$ subject to $\sum_{i=1}^k a_i=0$ where $a_i$ are integer? Specifically, which even integers can be ...
0
votes
1answer
18 views

Need an assistance with a specific step of a specific Division Algorithm proof

I'm trying to wrap my head around a Division Algorithm's proof. That is, Let $a, b \in \mathbb{Z}, a \neq 0$. Then there are unique $q,r \in \mathbb{Z}$ such that $b = qa + r, 0 \leq r < |a|$. ...
0
votes
1answer
30 views

If an integer $k$ is a divisor of an integer $n$, then $\frac{n}{k}$ is also a divisor of $n$?

A lot of these number theory ideas are popping up in my study of cyclic groups. In particular, in a note I came across. It is mentioned that: If an integer $k$ is a divisor of an integer $n$, ...
1
vote
3answers
54 views

How do I show that $\gcd(n,\frac{n}{k})=\frac{n}{k}$?

$\gcd(n,\frac{n}{k})=\frac{n}{k}$ Let $n, k$ be positive integers. This should be a trivial question but not having taken any classes in number theory I would like to be convinced with a simple ...
4
votes
2answers
111 views

Show that $233$ divides $2^{29} - 1$

Show that $233$ divides $2^{29} - 1$. At first I've tried to find some trivial congruence to brute force my way to the 29th exponent, however it seems that only $2^{29} \equiv 1 \pmod{233} $. ...
3
votes
1answer
32 views

Using the principle of inclusion-exclusion determine the number of prime numbers not exceeding 100.

Using the principle of inclusion-exclusion determine the number of prime numbers not exceeding 100. How would you approach this problem?
3
votes
2answers
32 views

Followup to question on $5$-adics, if $k \in \mathbb{Q}_5^\times$, is there $x_1, x_2, x_3 \in \mathbb{Q}_5$ where $\sum_{i = 1}^3 x_i^2 = k$?

This is a followup to my question here. My question is as follows. If $k \in \mathbb{Q}_5^\times$, then are there $x_1$, $x_2$, $x_3 \in \mathbb{Q}_5$ where$$x_1^2 + x_2^2 + 3x_3^2 = k?$$My idea is ...
3
votes
2answers
31 views

$p$-adics, elements of $\mathbb{Q}_5^\times/(\mathbb{Q}_5^\times)^2$?

Here is a question surrounding the $p$-adics. I am curious as to what the description of the quotient group $\mathbb{Q}_5^\times/(\mathbb{Q}_5^\times)^2$ is, i.e. what are its elements? Here is an ...
1
vote
1answer
28 views

Trouble understanding part of thereom: Every prime congruent 1 mod (4) can be written as sum of two squares.

I've been working through with great difficulty Dudley Underwood's Elementary Number Theory. I'm having some problem understanding the proof of a thereom regarding the sum of two squares. I still ...
2
votes
2answers
36 views

Find the set of $k \geq 3$ satifying $(k-2)|2k$

As a starting point, a solution claims that finding $k$ such that $(k-2)|2k$ is equivalent to finding $k$ such that $gcd(k-2,2k) = k - 2$. Why is this true? I can coherently post the rest, for the ...
-2
votes
3answers
92 views

Proof that if $3 \mid p^2$ then $3 \mid p$ [closed]

Course: Analysis (1st year course) Question: What does the formal proof of the following statement look like: if $3\mid p^2$ then $3\mid p$, with $p \in \Bbb Z$? Thank you. EDIT: I'd like to use ...
1
vote
4answers
31 views

Show that $\gcd(80,8a^2+1)=1$

Show that $\gcd(80,8a^2+1)=1$ Let $\gcd(80,8a^2+1)=d$, then we have: $d|80a^2+10,80a^2\Rightarrow\ d|10$ So $d=1\ or\ 2\ or\ 5\ or\ 10$ Obviously $d$ can't be $2\ or\ 10$,but how can we show $d$ can't ...
0
votes
0answers
21 views

Using hensel's lemma

I dont know why if f'(1)=0 mod3 , then f(1)=36 mod81 means there is no solution. we dont need to test each step? In mod3 's sold considering sol of mod9 And with sol of mod9. We decide sol of mod27 ...
0
votes
3answers
62 views

Show that among every consecutive 5 integers one is coprime to the others

Show that among every consecutive 5 integers one is coprime to the others I considered these 5 numbers as: $5k,5k+1,5k+2,5k+3,5k+4$ It's seen that for example $5k+1$ is coprime to $5k$ and $5k+2$,now ...
5
votes
1answer
225 views

Conjectured primality test for $F_n(28)=28^{2^n}+1$

How to prove that following conjecture 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 ...
1
vote
4answers
78 views

Find the sum to $n$ terms of the series $10+84+734+…$

Find the sum to n terms of the series $10+84+734+....$ $\frac{9(9^n+1)}{10} + 1$ $\frac{9(9^n-1)}{8} + 1 $ $\frac{9(9^n-1)}{8} + n $ $ \frac{9(9^n-1)}{8} + n^2$ My attempt: I'm getting option ...
1
vote
2answers
25 views

Cubic modular equation

If i found the sol of (a), i can find sol of (b) and (c) by using hensel's lemma i want to know the way of solving (a) without testing all the case (ex testing 1,2,3,4,...10) I think that there ...
1
vote
1answer
38 views

The exponent of $11$ in the prime factorization of $ 300!$ is___.

The exponent of $11$ in the prime factorization of $ 300!$ is $27$ $28$ $29$ $30$ My attempt: According to Exponent of $p$ in the prime factorization of $n!$ ...
1
vote
3answers
55 views

Is it true: $3k^2+1$ is a perfect square if and only if $k=1$ or $4$

I'm checking the following conjecture: $3k^2+1$ is a perfect square if and only if $k=1$ or $4$. If it is not true counter example would be appreciated. Thanks in advance.
2
votes
3answers
60 views

$\frac{1}{{{a_1}}} + \frac{1}{{{a_2}}} + \cdots + \frac{1}{{{a_n}}} < 2$

If ${{a}_{1}},{{a}_{2}},\ldots ,{{a}_{n}}$ are distinct odd natural numbers not divisible by any prime greater than 5, then show that $\frac{1}{{{a_1}}} + \frac{1}{{{a_2}}} + \cdots + ...
3
votes
3answers
34 views

Proof that $\sum_{d|m} |\mu(d)|=2^n$, where $n$ is the number of distinct prime divisors of $m$?

Given an integer $m$ such that $n$ is denoting the distinct prime divisors of $m$, is there a proof that the sum over the divisors of m of the absolute value of the Möbius function $\mu(d)$ is equal ...
1
vote
1answer
49 views

Show that there are no solutions to $x^2 + y^2 = 3z^2$ in $\Bbb{Z}$

I'm attempting to work through some of the questions in Whitelaw's "Introduction to Abstract Algebra" but am having some difficulty. The question is as follows Show that $\forall n \in \Bbb{Z},$ ...
0
votes
2answers
23 views

Proving that a common divisor of two variables is also a divisor of the sum of the two variables

if $k~|~a$ and $k~|~b$ then $k~|~as+bt$ for all $s,t \in \mathbb{Z}$ is what I'm trying to prove so I thought I should start by proving that $k~|~a+b$ if $k~|~a$ and $k~|~b$. since $a = \prod ...
5
votes
1answer
72 views

If $a \in \mathbb{Z}_5$ and $a \equiv \pm1 \text{ }(\text{mod }5)$, does there exist $x \in \mathbb{Z}_5$ where $x^2 = a$?

If $a \in \mathbb{Z}_5$ and $a \equiv \pm1 \text{ }(\text{mod }5)$, does there exist $x \in \mathbb{Z}_5$ where $x^2 = a$? I know we want to use Hensel's Lemma somehow to assess this question, but I'm ...
2
votes
2answers
37 views

If the sequence $ x_{n} $ converges to L, then $\lim_{k\to \infty}x_{k+1} = L $

Can someone read this proof and let me know if it is correct? If the sequence $ x_{n} $ converges to $L$, then $$\lim_{k\to \infty}x_{k+1} = L $$ Proof. Let $ \epsilon > 0$, and suppose ...
0
votes
3answers
57 views

Solve the following equation in $\mathbb{Z}_{16}$

I have this equation $\hat{5}x = \hat{6}$ in $\mathbb{Z}_{16}$. I'm not good at all at modular arithemetic. So far I just figured it out that $\hat{5}x = 6+16k, k\in \mathbb{Z}$.
4
votes
3answers
61 views

Quick, self-contained way to see why $\left({{-1}\over p}\right) = 1$?

Let $p$ be a prime number congruent to $1$ modulo $4$. What is a quick and self-contained way to see why$$\left({{-1}\over p}\right) = 1?$$
0
votes
1answer
53 views

How to solve this kind of Olympiad problems?

This kind of question is often asked in olympiads: Find the remainder when $a^n$ is divided by b where n is a very large number and a and b are whole numbers. What is the general trick to ...
2
votes
1answer
45 views

Given $p$ prime for some $p$ deduce $2p+1$ prime

Given $p=33179$ and $2^{2p+1}\equiv 2\; \pmod{2p+1}$, deduce $2p+1$ is prime. All I can think of is using Fermat's little theorem: $2^{2p}\equiv 1\pmod{2p+1}$ which just tells me it may be prime.
1
vote
1answer
33 views

root of quadratic equation in $Z_n$

I want to find criterion on $n$ satisfying this statement: "there is $x \in \mathbb{Z} _n$ such that $x^2 = a$". In case that $a=-1$, it is well known that (1) if $4k+1$ is prime, $n=4k+1$ satisfy ...
3
votes
1answer
78 views

How to prove that $n! = n^n - C_{n,1} (n-1)^n +C_{n,2} (n-2)^n - \cdots $?

How to prove that $n! = n^n - C_{n,1} (n-1)^n +C_{n,2} (n-2)^n - \cdots\,{} $? I faced this problem when trying to find the number of onto functions possible from one set having n elements to ...
1
vote
2answers
43 views

Help answering Pell Equation questions

I understand the Pell equation is $$x^{2}-dy^{2}=1$$ However I don't understand how to use this to get $(x,y)$ for these questions. 1) Find a nontrivial solution of $x^{2} − 3y^{2} = 1.$ 2) Find ...
2
votes
3answers
57 views

Show that $\gcd(a,b)=d\Rightarrow\gcd(a^2,b^2)=d^2\ $ [duplicate]

Show that if $\gcd(a,b)=d\Rightarrow\gcd(a^2,b^2)=d^2\ $ $\gcd(a,b)=d\Rightarrow\ d\mid a,b\Rightarrow\ \ d^2\mid a^2,b^2\Rightarrow\ d^2\mid\gcd(a^2,b^2)$. But to complete the proof we must show ...
0
votes
0answers
39 views

How to generate the sequence of prime building blocks of the colossally abundant numbers: $2, 3, 2, 5, 2, 3, 7, 2, 11, 13, 2, 3, 5, 17, 19, 23, 2,…$

This is the sequence of prime numbers which are the elementary building blocks for the superior highly composite numbers: $2, 3, 2, 5, 2, 3, 7, 2, 11, 13, 2, 3, 5, 17, 19, 2, 23, 7, 29, 3, 31, 2, 37, ...
0
votes
1answer
10 views

Factors/divisibility of monotonically-increasing integer polynomial

For positive integers $n$ and $x$, let $f_n(x)$ be a polynomial in $x$ of degree $n-1$, such that $f_n(x)$ is monotonically increasing for increasing $x \ge 1$. Now assume that there exist positive ...
3
votes
1answer
70 views

How do I count the solutions of $m^2 + m n + n^2 = T$?

I've come across this problem in my studies. I was wondering if there is a better algorithm for it: Given a fixed positive integer $T$, count the solutions of $$n^2 + n m + m^2 = T$$ where $m$ and $n$ ...
5
votes
1answer
261 views

Limit of Euler's Totient function

Clearly if $p$ is prime, the sequence $\frac{\phi(p)}{p} \rightarrow 1$. In general, however, if $s_n \in S \subseteq \mathbb{N}$, we are not even guaranteed of the existence of: $\displaystyle ...
1
vote
0answers
38 views

More efficient RSA using Chinese Remainder Theorem

Is there a way to increase the efficiency of the RSA algorithm by incorporating elements of the Chinese Remainder Theorem?