# Tagged Questions

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

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 ...
55 views

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
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 ...
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 ...
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|$. ...
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$, ...
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 ...
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}$. ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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!$ ...
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.
60 views

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 ...
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 ...
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}$.
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?$$
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 ...
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.
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 ...
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 ...
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 ...
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 ...