# Tagged Questions

Questions on more advanced topics of number theory, such as quadratic residues, primitive roots, prime numbers, non-linear Diophantine equations, etc. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

52 views

### Find pairs $(a,b)$ with $\gcd(a,b),\gcd(a + 1, b),\ldots, \gcd(a + k, b)$ given

Given a set of GCD's, how to find a set of numbers that satisfy all their criteria? Suppose we are given a $k$ integers $\gcd(a,b),\gcd(a + 1, b),\ldots, \gcd(a + k, b)$ for some k. How to get a and b ...
22 views

15 views

### How can I prove this is a reduced residue system?

The problem is [Let m>=3 be a positive integer and let Zm* = {s1,s2,s3...,sφ(m)} denote the standard reduced set of residues modulo m. Derive that s1+s2+...+sφ(m)=φ(m)/2 * m] So I tried to make set T:...
27 views

### Well ordering axiom problem

Show that if a and b are positive integers, there is a positive integer n such that $na>b$. Hint: Consider the differences $b-na$, and apply the well ordering axiom. I have no approach yet. My ...
69 views

### Maximal bounds for a variable

If $p$ and $q$ are distinct prime numbers, then there are integers $x_0$ and $y_0$ such that $$1 = px_0+qy_0.$$ Determine the maximum value of $b-a$, where $a$ and $b$ are positive integers with the ...
28 views

### Explaining a Series Expansion for the Divisor Function

The "sum-of-divisors" function, defined as $\sigma(n)=\sum_{d\,\mid\,n}d$, can be expressed as $$\sigma(n)=\sum_{i=1}^n\sum_{j=1}^i\cos\Big(2\pi n \frac{j}{i}\Big)$$This expansion makes logical sense. ...
177 views

34 views

### How can I solve binomial congruent equations?

[Determine whether or not the quadratic congruence $2x^2+5x-9=0\pmod {101}$ is solvable.] I make it to perfect square form and use Legandre symbol. $2(x+77)^2 = 60 \pmod{101}$ Is there any ...
116 views

50 views

### Simplifying a Double Summation

Let $f_n(k)$ be defined as $$f_n(k)=\sum_{i=1}^n\sum_{j=1}^i\left(\frac{j}{i}\right)^k$$ Can $f_n(k)$ be simplifying down to an expression without summations? By simply graphing $f_n(k)$, it is clear ...
23 views

### Maximum length of subset such that all elements are coprime

Given an array, we have to find the length of maximum subset such that all elements of that subset are coprime. That is for $a[i],a[j]$ belonging to subset $\gcd(a[i],a[j]) = 1$ for all distinct $i,j$....
43 views

### How do I find the sum using non-brute force method?

How many number $X$ less than $350$ exist such that the sum of the number of divisors of X and the number of divisors of the square of $X$ is $60$ I know how to find the number of divisors without ...
29 views

### Number of distinct equivalence classes of $\mathbb Z_n$ of the “ associate ” equivalence relation

Define an equivalence relation on $\mathbb Z_n$ as : For $a,b \in \mathbb Z_n$ , $a\sim b$ iff $\exists k \in U_n=\mathbb Z_n^{\times}$ such that $a=kb$ (i.e. $a,b$ are related if they are "...
50 views

### Primes is in P, proof of hendrik Lenstra Jr. lemma

In the paper describing AKS primality test : http://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf On page no. 8 Lemma 4.7 last paragraph, I cannot understand how number of ...
48 views

### Elliptic curves over $\mathbf{F}_q$ with $q = p^{2m}$

I am reading Washingtons book about elliptic curves and struggling with an exercise there (4.9), which is the following: Let $E$ be an elliptic curve over $\mathbf{F}_q$ with $q = p^{2m}$. Suppose ...
28 views

### Question about multiplicative arithmetic functions

Let $f,g:\Bbb N\to \Bbb C$ be multiplicative arithmetic functions, i.e. $$\gcd(m,n)=1\implies f(mn)=f(m)f(n)$$ and same for $g$. We can also assume $f(1)\neq 0$ and $g(1)\neq 0$ if necessary. How can ...
25 views

118 views

### How to calculate $9^{47^{51}} \mod 67$?

I've looked at some other related things on here, but this seems a little more complicated with the double exponentiation. Is there a general algorithm to calculate $a^{c_1^{c_2^{...^{c_n}}}} \mod p$ ...
56 views

### Prove that a Fermat Number cannot be a Carmichael Number?

Prove that a Fermat Number cannot be a Carmichael number: Fermat numbers are of the form $2^{2^n}+1$ and $F$($n$) denotes the $n$th Fermat number. If $F$($n$) is a Carmichael number, that would mean ...
88 views

### Prove *directly*: Even perfect squares have even square roots.

Is it possible to prove directly that even perfect squares have even square roots? Or, symbolically: $\forall n \in \mathbb{Z},\ \ n^2 \text{ is even } \Rightarrow n \text{ is even }$ The indirect ...
85 views

### Counting the number of partitions

Let $P$ be a set of $7$ different prime numbers and $C$ a set of $28$ different composite numbers each of which is a product of two (not necessarily different) numbers from $P$. The set $C$ is divided ...