Multiplicative independence explained

In number theory, two positive integers a and b are said to be multiplicatively independent^[1] if their only common integer power is 1. That is, for integers n and m,

a ^{n=b} ^{m} implies n = m =0 . Two integers which are not multiplicatively independent are said to be multiplicatively dependent.

As examples, 36 and 216 are multiplicatively dependent since

36 ^{3=(6} ^{2)} ^{3=(6} ^{3)} ^{2=216} ^{2} , whereas 2 and 3 are multiplicatively independent.

Properties

Being multiplicatively independent admits some other characterizations. a and b are multiplicatively independent if and only if

log (a)/ log (b) is irrational. This property holds independently of the base of the logarithm.

Let

a = p ^{\alpha _{1}} _{1} p ^{\alpha _{2}} _{2} … p ^{\alpha _{k}} _{k} and b = q ^{\beta _{1}} _{1} q ^{\beta _{2}} _{2} … q ^{\beta _{l}} _{l} be the canonical representations of a and b. The integers a and b are multiplicatively dependent if and only if k = l, p _{i=q} _{i} and (\alpha _{i})/(= \beta _{i}) (\alpha _{j})/(\beta _{j}) for all i and j.

Applications

Büchi arithmetic in base a and b define the same sets if and only if a and b are multiplicatively dependent.

Let a and b be multiplicatively dependent integers, that is, there exists n,m>1 such that

a ^{n=b} ^{m} . The integers c such that the length of its expansion in base a is at most m are exactly the integers such that the length of their expansion in base b is at most n. It implies that computing the base b expansion of a number, given its base a expansion, can be done by transforming consecutive sequences of m base a digits into consecutive sequence of n base b digits.

References

^[2]

Notes and References

1. Web site: Bès. Alexis. A survey of Arithmetical Definability. 27 June 2012. dead. https://archive.today/20121128154616/http://130.203.133.150/viewdoc/summary?doi=10.1.1.2.2136. 28 November 2012.
2. Bruyère. Véronique. Véronique Bruyère. Hansel. Georges. Michaux. Christian. Villemaire. Roger. Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. 1994. 1. 191--238.